地図では近く見える道を選んだのに、大きく迂回した車の方が先に着くことがある。移動する距離と、到着までの時間は別の量だからである。経路を選ぶ問題では、何を最小にしたいのかを決めることが、計算の出発点になる。
道路へ、距離とは別の値を付ける
交差点を点、交差点を結ぶ道路を線で表すと、道路網をグラフとして扱える。それぞれの線へ距離を付け、その合計が最小になる道を探せば、距離で見た最短経路になる。同じ線へ所要時間を付ければ、時間の合計を最小にする問題へ変わる。
説明のため、2kmの道を平均時速20km、3kmの道を平均時速60kmで進めるとする。所要時間はそれぞれ6分と3分で、長い道の方が早い。信号や加減速を省いた仮定であるが、距離の大小だけでは到着順が決まらないことが分かる。
目の前の近道を選ぶだけでは足りない
今いる交差点から最も短い道路へ進むことを繰り返しても、目的地までの合計が最小になるとは限らない。その先に大きな迂回が待つ場合があるからである。経路探索では、途中までにかかった費用と、その先につながる経路を組み合わせて比べる。
代表的なDijkstra法は、各区間の重みが負でないグラフで、出発点からの最短経路を求める方法である。ここでいう重みを距離にするか時間にするかによって、求める道が変わる。「最短」という数学上の名称には、道路の長さ以外を最小にする問題も含まれるのである。
時間の予測が変われば、答えも変わる
実際の道路では、同じ区間でも時間帯や混雑によって所要時間が変わる。右折待ちなど、直前にどこから来たかが次の移動へ影響する場合もある。こうした条件を扱うには、単純な道路の長さに加え、時刻や曲がり方を表す情報が必要になる。
計算が正しくても、入力した所要時間の予測が外れれば、実際には別の道が早かったという結果が起こる。料金、乗換回数、歩きやすさを重視すれば、選ぶ基準も変わる。最適な経路とは、指定した条件と評価の物差しに対して、最もよい経路なのである。
グラフの「重み」は、区間へ割り当てた数値である。物理的な重量を意味せず、距離、所要時間、料金など、問題に応じた量を表す。
参考資料
- Princeton University：Algorithms, 4th Edition — Shortest Paths
- Princeton University：DijkstraUndirectedSP
参考資料確認日：2026年10月14日。