2

次のグラフがあるとします。

           e (destination)
           |
           | (1)
           |
           d
           |
           | (100)
           |
  (start)  a - - - b - - - c
             (1)      (1)

ダイクストラのアルゴリズムは行き止まりになりますか？aから始めると、a-> b-> cになって行き止まりになり、eに到達できないと思います。そうですか？

4

1 に答える 1

3

明らかにそうではありません。Dijkstraのアルゴリズムのウィキペディアの説明から：

.3. 現在のノードについて、未訪問のすべての隣接ノードを考慮し、それらの暫定的な距離を計算します。

つまりa、bとで開始した場合d、それらは未訪問の隣人であるため、両方とも検査されます (つまり、それらの暫定的な距離が計算されます)。bの方が仮距離が小さいので、次にそちらを訪問します。

追加ノードを使用した更新の場合:上記のようにe到達します。cしかし、行き詰っているわけではありません。つまり、事前に計算された暫定的な距離を持つ未訪問のノードがまだあるdので、次にそのノードにアクセスします。

于 2013-02-12T04:15:33.300 に答える