ダイクストラアルゴリズムの理解

Question

私は、最短経路を見つけるためのダイクストラアルゴリズムを理解しようとしています。

この例では、トップテーブルが左下隅の画像に対応しています。今

、私の問題は、私は、ステップ2にステップ1からの移行を理解していないということです。

我々はUXにある場合、我々はにXのコストを追加することによって、UXVに旅行することができますV（これは2）を現在のコスト（1、UXのコスト）に換算したものです。だから、合計は3になるだろうが、これより大きいので、私たちは既に2を見つけたので、私たちはそれを変更しない。ステップ1では、同じコストを持つ2つのオプションがあります。 UXYとUXVではなく、アルゴリズムがUXVの代わりにUXYに行くことを選択する理由は何ですか？

ありがとうございます！

Answer 1

同じコストで2つ以上のオプションがある場合、どのオプションを先に進めても差はありません。

Dijkstra's algorithm Wikipedia articleには、アルゴリズムを実装するための擬似コードを持つセクションがあります。擬似コードにはu ← vertex in Q with min dist[u]という行があることがわかります。これは最低のコストで1つのオプションを選択することを意味します。同じコストでより多くの選択肢がある場合は、それらのいずれかを取るだけです。

具体的には、UXYの代わりにUXVに行くこともできます。このはさらに多くのステップにつながりますが、アルゴリズムが終了すると最終結果は同じになります。