ダイクストラの最短パスアルゴリズム同じ距離のパスがある場合はどうなりますか？

Question

このネットワークでは、ダイクストラの最短パスアルゴリズムが使用されます。 質問は、両方が等しいのでAがDに達するためにどのパスを使用するのでしょうか？

そのテーブルが欠落していますか？

Answer 1

実際の実装と入力グラフの記述方法によって異なります（例：エッジの順序が異なる場合があり、多くの場合は結果に影響します）。

ただし、の一部がの最適な長さのパスになることが保証されています。

EとFの頂点でテーブルが間違っているようです。 Eの親頂点はD（AB→BD→DE = 3 + 4 + 2 = 9）であり、Fも同様である。

Answer 2

緩和関数の実装に依存する。たとえば、algorithm described in the wikipediaはの比較を厳密に使用します。if alt < dist[v]です。この場合（および私が見たすべての実装で）AからDまでの最短経路はA -> B -> Dです。

なぜですか？そのため（S =落ち着いたノードとノードのQ =キュー、距離のペア、親）：あなたはQからS = {A:0}とQ = {B:3,A C:5,A D:9,A}

を得るようBを選択し、それをリラックス、Aを緩和

1. スタート。あなたはS = {A:0 B:3,A}とQ = {C:(5,A) D:7,B E:10,B}
2. からQCを選択してそれをリラックスしてください。 S = {A:0 B:3,A C:5,A}とQ = {D:7,B E:10,B}が得られます。
3. QDを選択すると、アルゴリズムを終了することができます。

新しいパスが現在のパスよりも優れていないので、ステップ3で、あなたはDの親を変更する必要はありません。緩和アルゴリズムがless-than-or-equalの比較を使用する場合、結果は異なります。