ダイクストラ法 とは？

経路を考える例としてはわかりやすいね。交差点を頂点、道路を辺、長さや時間を重みとして表せる。その重みが0以上なら、出発地からの重みの合計が最小になる経路を調べられるよ。OSPFという通信の規格でも、最短経路木の計算に使われているんだ。

始点の距離を0、他の頂点を無限大にする。未確定の頂点のうち、始点からの暫定距離が最小のものを選び、そこまでの距離を確定するよ。隣へ進む経路の合計が既知の距離より短ければ更新し、同じ操作を繰り返すんだ。

そうだよ。暫定距離が最小の頂点を、優先度付きキューで選ぶ実装もある。ここでいう距離は地図上の直線距離ではなく、始点から辺の重みを足した値なんだ。到達できない頂点の距離は無限大のままで、そこへの経路は見つからないよ。

この方法の前提は、辺の重みが0以上であることだよ。負の重みがある場合は、ベルマン・フォード法などの別の方法と、その適用条件を検討する。始点から到達できる、重みの合計が負になる閉路のために、最短距離そのものが定まらない場合もあるんだ。