graph - 無向加重グラフの2つのノード間の異なる最短経路の総数を線形時間で見つけますか?

Question

重み付きグラフ G(V,E) があり、その中の任意の 2 つの頂点 S と T の間の最短経路を 1 つ見つける必要がある場合、ダイクストラス アルゴリズムを使用できたのではないかと考えていました。しかし、S から T への個別の最短経路をすべて見つける必要がある場合に、これをどのように行うことができるかわかりません。O(n) 時間で解決できますか? グラフのエッジの重みが特定の範囲の値のみを想定できると仮定すると、1 <=w(e)<=2 とします。これは時間の複雑さに影響しますか?

Answer 1

ダイクストラを使用してそれを行うことができます。ダイクストラのアルゴリズムでは、ソースからの距離に基づいて各ノードにラベルを割り当て、この距離に従ってノードを解決します (小さい方から)。ターゲット ノードが確定すると、最短パスの長さが得られます。パス (= エッジのシーケンス) を取得するには、解決した各ノードの親を追跡できます。可能なすべてのパスを取得するには、各ノードの複数の親を考慮する必要があります。

小さな例:

次のようなグラフがあるとします (簡単にするために、すべてのエッジの重みは 1 です)。

       B
      / \
     A   C - D
      \ /
       E

ダイクストラを実行して距離 A->D を見つけると、3 になります。最初にノード A を距離 0 に設定し、次にノード B と E を距離 1 に設定し、ノード C を距離 2 に設定し、最後にノード D を距離 3 に設定します。パスを取得するには、ノードを解決するときにノードの親を覚えておく必要があります。この場合、最初に B と C の親をノード A に設定します。次に、ノード C の親を B と E に設定する必要があります。これらは両方とも同じ長さを提供するからです。ノード D はノード C を親として取得します。

パスが必要な場合は、D から始まり、ノードが複数の親を持つたびに分岐して、親ポインターをたどることができます。これにより、ノード C にブランチが作成されます。

上記のコメントで言及されている投稿は同じ原則を使用していますが、実際にパスを抽出することはできませんが、カウントのみを提供します. 最後に 1 つ: Dijkstra は、キューとノード セットを維持するために多くの操作を行う必要があるため、線形時間アルゴリズムではありません。