私は DAG を持っており、任意のノードから別のノードへのすべてのパスをカウントする必要があります。少し調査したところ、いくつかのトポロジー順序で実行できることがわかりましたが、これまでのところ、ソリューションは不完全または間違っています。
では、どのように行うのが正しいのでしょうか。
ありがとう。
私は DAG を持っており、任意のノードから別のノードへのすべてのパスをカウントする必要があります。少し調査したところ、いくつかのトポロジー順序で実行できることがわかりましたが、これまでのところ、ソリューションは不完全または間違っています。
では、どのように行うのが正しいのでしょうか。
ありがとう。
これは DAG であるため、ノードを O(V+E) 時間でトポロジカルに並べ替えることができます。ソース頂点が S であると仮定しましょう。次に、S から最初に深さ方向にノードを走査し始めます。ノード U を処理しているとき、エッジ U->V があると仮定すると、もちろん V はまだ訪問されていません (なぜですか? それは有向非巡回グラフだからです) したがって、d[U のノード U を介して S から V に到達できます。ここで、d[U] は S から U へのパスの数です。
したがって、S から任意のノード V へのパスの数、d[V] = d[x1]+d[x2]+d[x3]+ . . . +d[xy]、x1->V、x2->V、. . . xy->V
このアルゴリズムは、O(V+E) を使用してグラフをトポロジカルに並べ替え、次に最大で O(V*E) のパス数を計算します。隣接行列の代わりに隣接リストを使用して、O(V+E) へのパス数を計算する実行時間をさらに短縮できます。これは、これまでのところ最も効率的なソリューションです。
再帰を使用して、ツリー/DAG 内のすべてのパスをカウントできます。擬似コードは次のとおりです。
function numPaths(node1, node2):
// base case, one path from node to itself
if (node1 == node2): return 1
totalPaths = 0
for edge in node1.edges:
nextNode = edge.destinationNode
totalPaths += numPaths(nextNode, node2)
return totalPaths
編集: この問題に対する優れた動的アプローチは、Floyd-Warshall アルゴリズムです。