重み付きグラフの問題を解く「ダイクストラ法」

前回の記事では、重みなしグラフの最短経路問題を解くアルゴリズムである「幅優先探索」を説明しました。

しかし、高速道路の所要時間（下図）など、現実の問題設定の多くは重み付きグラフで表されます。そのため、例えば「高井戸 IC から名古屋 IC までの最短時間は何分か?」という問題に答えたい場合、重み付きグラフの最短経路問題を解く必要があるのです。

では、重み付きグラフの最短経路問題はどうやって解けば良いのでしょうか。今回の記事では、一つの解決策として「ダイクストラ法」を紹介します。

ダイクストラ法とは

ダイクストラ法は、以下の 2 つのルールにしたがって、最短経路長を求めるアルゴリズムです。

ルール1　スタートに近い頂点から順番に、答えを確定させていく
ルール2　答えが確定したら、その頂点に隣接する頂点の最短経路長を更新する

例として、上図の高速道路における、高井戸 IC から各地点までの最短時間を求めることを考えましょう。