ダイクストラ法

ダイクストラ法は、負の重みがないグラフで、出発点からほかのすべての頂点への最短経路を求める方法です。

■ 試験で押さえるポイント

• まだ確定していない頂点のうち、距離が最小の頂点を確定することを繰り返します。

• 確定した頂点から、隣の頂点の距離を更新します。

• 負の重みの辺があると、正しく求められません。

■ 過去問での着眼点

距離が最小の頂点から順に確定していく点を押さえます。

例: カーナビで、出発地から目的地までの最短の道を求めます。