ダイクストラ法 — 重み付きグラフの最短経路

遠回りのほうが速いことがある

前のレッスンでは、辺 1 本を 1 歩と数えて最短の歩数を求めました。現実の地図はそうなっていません。同じ 1 本の道でも、5 分の道と 40 分の道があります。

出発から B へは、直通なら辺 1 本で 4 かかります。A を経由すると辺は 2 本になりますが 1 + 2 = 3 です。乗り換えが増えるほうが安い。辺の本数で測る幅優先探索は、ここで間違えます。近い順に広げるという前提そのものが、重みが入った瞬間に成り立たなくなるからです。

辺に重みが付いた最短経路を求めるのがダイクストラ法です。カーナビも、ルーターの経路計算も、配送順の計算も、根っこはこれです。

一番安い未確定を確定する

各点に「今わかっている最小のコスト」を持たせます。出発点は 0、ほかは無限大から始めます。

繰り返すのは次の 2 つだけです。

1. まだ確定していない点のうち、コストが一番小さい点を選んで確定する
2. 確定した点の隣を見て、「確定した点のコスト + 辺の重み」が隣の今の値より小さければ、その値に書き換える

上の図で追ってみます。最初に確定するのは出発点で 0。隣を見て A が 1、B が 4 になります。未確定で一番小さいのは A の 1 なので A を確定。A の隣を見て B が 1 + 2 = 3 に下がり、C が 1 + 5 = 6 になります。次に確定するのは B の 3。B の隣を見て C が 3 + 1 = 4 に下がります。次は C の 4 で、目的地が 4 + 3 = 7。

大事なのは、一度確定した点の値はもう変わらない ことです。未確定のなかで一番安い点に、これ以上安い行き方があるとしたら、それは今より高い点を経由することになります。重みが 0 以上なら、経由するほど高くなるので、安くなりようがありません。だから目的地を確定した瞬間に、そこで止めて答えを返せます。

負の重みがあると、確定が嘘になる

この「安くなりようがない」は、重みが 0 以上だから言えることです。マイナスの辺が 1 本でもあると崩れます。

出発から A への重みが 3、出発から B への重みが 2、A から B への重みが -2 だとします。ダイクストラ法は、未確定で最小の B を先に 2 で確定します。ところが実際は、遠回りして A を通ると 3 + (-2) = 1 で着けます。確定したあとに、もっと安い道が出てきてしまいました。

マイナスの重みは、値引きや払い戻しを辺に載せたときに出てきます。そういうときはベルマン・フォード法という別の道具を使います。

解説

重みが無いなら幅優先探索、重みがあるならダイクストラ法、マイナスが混じるならベルマン・フォード法。この 3 段で覚えておくと迷いません。

やってみよう

• 上の図で、目的地までの最小コストが 7 になることを手で確かめる
• A から C への辺を 5 から 2 に変えると、通る道はどう変わるか
• 全部の辺の重みを 1 に揃えると、答えが「歩数」と一致することを確かめる