ダイクストラ法

ダイクストラ法とは

グラフの辺に値を持たせたグラフを重みつきグラフと呼ぶ。そして、そのスタート地点から目的点までの最短経路を求める問題を最短経路問題と言います。最短経路を求める代表的なアルゴリズムがダイクストラ法です。

ダイクストラ法は、各頂点への最短距離をスタート地点の隣接点から一つずつ確定する。