グラフ内の2つのノード(スパース、有向、およびサイクルを含む)間の単純なパス(ノードが繰り返されない)の総数を計算することに興味があります。グラフは強連結成分です。
最初に、行列乗算を使用してみました。ここでは、隣接行列を 2 から n-1 のすべての累乗に上げました。n はノードの数です。ただし、これはグラフの循環のために失敗します。DAG の場合、これらすべてのパワーを計算して合計するだけで十分です。
質問する
992 次
2 に答える
1
この問題に対する効率的なアルゴリズムはありません。
頂点sからtへの単純なパスの数を数える問題は、#P 完全です。したがって、一般的に機能する多項式時間アルゴリズムを期待することはできません。たとえば、https://cstheory.stackexchange.com/q/20246/5038、https://stackoverflow.com/a/5570751/781723、https://cs.stackexchange.com/q/423/755を参照してください。
この問題の解決を回避する方法や、近似アルゴリズムなどを使用する方法を見つけようとする時が来ました。
于 2014-06-01T23:39:10.473 に答える