0

私は DAG を持っており、任意のノードから別のノードへのすべてのパスをカウントする必要があります。少し調査したところ、いくつかのトポロジー順序で実行できることがわかりましたが、これまでのところ、ソリューションは不完全または間違っています。

では、どのように行うのが正しいのでしょうか。

ありがとう。

4

3 に答える 3

2

これは 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) へのパス数を計算する実行時間をさらに短縮できます。これは、これまでのところ最も効率的なソリューションです。

于 2013-07-15T02:41:26.200 に答える
1

再帰を使用して、ツリー/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 アルゴリズムです。

于 2013-07-15T02:08:01.910 に答える