STAGE 7
ダイクストラ法
道に長さがあるときの最短経路
🎯 ミッション
ダイクストラ法の手順と、いちばん近い町から確定してよい理由・道の長さが0以上という条件を説明できるようになろう。S から全部の町までの最短距離を求め、確認クイズに全問正解すれば合格。
未達成

ねこ博士
前のステージの最後の問題だ。道ごとに長さ(距離)が違うとき、S から各町への最短の距離を求めたい。幅優先探索は「本数」の最短しか分からなかった。

うさ美
本数が少なくても遠回りのことがありますよね。2本の短い道のほうが、1本の長い道より近いこともある。

ねこ博士
そう。そこで、1959年にエドガー・ダイクストラが考えた方法を使う。考え方の中心はこうだ。「まだ距離が確定していない町のうち、今の時点でいちばん近いと分かっている町は、もうそれ以上近くならないので、確定してよい」。

うさ美
どうして「もう近くならない」と言えるんですか?

ねこ博士
確かめてみよう。いちばん近い町を X、その仮の距離を d とする。もし、ほかの道を通って X に d より近く行けたとしたら、その道は、どこかで「まだ確定していない町」Y を通るはずだ。Y の仮の距離はどうなっているかな。

うさ美
X がいちばん近いので、Y の仮の距離は d 以上。そこから X まで、さらに道を通るので……道の長さが0以上なら、合計は d 以上になる。d より近くはならない。だから X は d で確定していい、ということですか?

ねこ博士
そう。今の証明で、道の長さが0以上という条件を使ったね。もしマイナスの長さの道があったら、遠回りしたあとで距離が減ることがあり得るので、この方法は正しい答えを出せない。これがダイクストラ法の前提条件だ。
① S の距離を 0、ほかは ∞(まだ分からない)とする
② まだ確定していない町のうち、距離がいちばん小さい町を選んで確定する
③ その町から道でつながる町について、「確定した町の距離 + 道の長さ」が今の仮の距離より小さければ書き直す
④ 全部の町が確定するまで ②③ をくり返す(前提:道の長さはすべて0以上)

ねこ博士
ここで、手間を考えよう。②で「いちばん小さい町」を探すとき、まだ確定していない町を毎回全部見比べると、町の数 V に対して1回 O(V)、それを V 回くり返すので O(V²) になる。

うさ美
いちばん小さいものを、もっと早く取り出せればいいですね。

ねこ博士
そのための道具が優先度付きキューだ。中のものを、優先度(ここでは距離)の小さい順にすぐ取り出せるように工夫した入れ物で、よく使われる作り方(ヒープと呼ばれる木の形)なら、入れるのも取り出すのも O(log V) でできる。これを使うと、ダイクストラ法全体の計算量は、道の数を E として O((V+E) log V) になる。町が多くて道が少ない地図なら、O(V²) よりずっと速い。

うさ美
地図アプリの道案内も、これを使っているんですか?

ねこ博士
基本の考え方はこれだ。ただ、日本中の道を全部確定していたら遅すぎるので、ゴールの方角を優先して調べる工夫(A* と呼ばれる方法)や、高速道路のような大きな道だけを先にまとめて計算しておく工夫を重ねている。
確認クイズ
Q1. ダイクストラ法で、まだ確定していない町のうち距離がいちばん小さい町を「確定してよい」理由は?
正解! 回り道は、仮の距離が d 以上の未確定の町を通る。道の長さが0以上なら、合計は d 以上になる。
Q2. ダイクストラ法が正しい答えを出せない地図は?
正解! マイナスの道があると、遠回りのあとで距離が減ることがあり、「いちばん近い町は確定してよい」が成り立たない。行けない町は距離が ∞ のまま残るだけ。
Q3. 優先度付きキューを使うと、ダイクストラ法が速くなる理由は?
正解! 毎回全部見比べると O(V)。優先度付きキューなら O(log V) で取り出せ、全体で O((V+E) log V)。