ダイクストラ法 — 最短経路をステップごとに理解

ダイクストラ法は、重み付きグラフにおいて1つの開始ノードからの最短経路を求めるアルゴリズムです。ただし、すべての辺の重みが非負である必要があります。1つの目的地だけが必要なら、そのノードが確定した時点で処理を止められます。

中心となる考え方は貪欲法です。つまり、まだ確定していないノードのうち、既知の距離が最も小さいものから常に先へ進みます。これが正しく働くのは、辺の重みが非負である場合に限られます。

ダイクストラ法で解けること

ダイクストラ法は、辺にコストが付いたグラフで最も安い経路を求めたいときに使います。コストは距離、移動時間、エネルギー、あるいは最小化したい別の量を表していてもかまいません。

有向グラフでも無向グラフでも使えます。重要な条件は明確で、すべての辺の重みが少なくとも $0$ でなければなりません。

アルゴリズムの仕組み

各ノードは、開始ノードからの暫定距離を持ちます。最初は開始ノードの距離を $0$、それ以外のすべてのノードの距離を $\infty$ にします。

その後、次のループを繰り返します。

1. 未確定ノードの中から、暫定距離が最も小さいノードを選ぶ。
2. そのノードを通る各隣接ノードを調べる。
3. 新しい経路のほうが安ければ、隣接ノードの距離を更新する。
4. 現在のノードを確定済みにする。

ステップ3は緩和と呼ばれます。グラフに負の重みの辺がなければ、確定したノードの最短距離は最終的な値になります。

ダイクストラ法をステップごとに見る

手順全体を簡潔にまとめると、次のようになります。

1. 開始ノードを選ぶ。
2. その距離を $0$、それ以外のすべての距離を $\infty$ にする。
3. 未確定ノードの中から、暫定距離が最も小さいノードを選ぶ。
4. そのノードから出る辺を緩和する。
5. そのノードを確定済みにする。
6. 到達可能なすべてのノードが確定するまで繰り返す。あるいは、目的ノードが確定した時点で止める。

各更新を引き起こした直前のノードも記録しておけば、最終距離だけでなく実際の経路も復元できます。

最短経路の具体例

次のような辺の重みをもつグラフを考えます。

• $A \to B = 4$
• $A \to C = 1$
• $C \to B = 2$
• $B \to D = 1$
• $C \to D = 5$

$A$ から $D$ への最短経路を求めたいとします。

最初の状態は次のとおりです。

$$\text{dist}(A)=0,\quad \text{dist}(B)=\infty,\quad \text{dist}(C)=\infty,\quad \text{dist}(D)=\infty$$

まず $A$ を確定し、その辺を緩和します。

$$\text{dist}(B)=4,\quad \text{dist}(C)=1$$

この時点で未確定の中で最小の距離は $C$ なので、次に $C$ を確定します。

$C$ を経由すると、

• $C$ を通る $B$ への経路のコストは $1+2=3$ で、$4$ より小さいので $\text{dist}(B)=3$ に更新します。
• $C$ を通る $D$ への経路のコストは $1+5=6$ なので、$\text{dist}(D)=6$ とします。

次に未確定の中で最小の距離をもつのは $B$ なので、$B$ を確定します。

$B$ を経由すると、$D$ への経路のコストは

$$3+1=4$$

となります。

これは $6$ より小さいので、$\text{dist}(D)$ を $6$ から $4$ に更新します。

これで $D$ が未確定の中で最小のノードになります。$D$ を確定して終了です。

最短経路は

$$A \to C \to B \to D$$

で、合計コストは

$$1+2+1=4$$

です。

この例が示している重要な点は、最初は不利に見えた $A \to B$ という経路が、あとから $C$ を経由することでより良くなったということです。ダイクストラ法では、$B$ がまだ未確定である限り、そのような更新が可能です。いったんノードが確定すると、その距離はもう変わりません。

なぜ非負の重みが重要なのか

いま、未確定ノードの中で最も安いノードの距離が $d$ だとします。そのノードへの新しい経路があとから見つかるとしたら、それは暫定距離が少なくとも $d$ である別の未確定ノードから来て、さらに重みが少なくとも $0$ の辺を足すことになります。

したがって、そのあとから見つかる経路が $d$ を下回ることはありません。これが、すべての重みが非負であるときに、最小の暫定距離を確定してよい理由です。

負の辺があると、この議論は成り立ちません。今は高く見える経路があとで安くなる可能性があるため、ノードを早く確定しすぎると誤った答えになることがあります。

ダイクストラ法でよくあるミス

負の辺があるのに使う

負の辺が1本あるだけでも、貪欲な考え方は崩れます。負の重みがありうるなら、別の最短経路アルゴリズムを使う必要があります。

「見つけた」と「確定した」を同じだと考える

ノードに暫定距離が入っていても、まだ処理は終わっていない場合があります。最短距離が最終確定しているのは、確定済みのノードだけです。

直前ノードの表を忘れる

距離だけならコストはわかります。実際の経路も欲しいなら、各距離を最後に改善したノードも記録しておきましょう。

ダイクストラ法の使い道

ダイクストラ法は、問題を非負コストをもつグラフ上の移動として表せるときに使われます。

• 地図上の経路探索
• ネットワークルーティング
• 重み付きグリッド上でのロボット移動
• 移動コストが変化するゲームの経路探索

また、正しさが厳密な条件に依存する貪欲アルゴリズムの代表例でもあります。

似た問題に挑戦してみよう

5つのノードと正の辺の重みをもつグラフを自分で描き、距離表を使って手でダイクストラ法を実行してみましょう。次の一歩としては、新しいグラフで自分なりに試し、各ノードがいつ確定してよくなるのかを正確に確認してみるのがおすすめです。