最短経路問題（ダイクストラ・ベルマンフォード）

🎓 レベル：基礎　|　重要度：A（必須）

📎 前提：代表的な組合せ問題　|　関連：最大流・最小カット・動的計画法とベルマンの原理

要点（BLUF）

最短経路問題は、グラフ上で2ノード間の 最小重み経路を求める。動的計画法（動的計画法とベルマンの原理）の代表例。
ダイクストラ法：辺の重みが非負なら、貪欲に確定ノードを増やして $O(E + V\log V)$ で解ける。
ベルマンフォード法：負の辺があっても解け、緩和を $V-1$ 回繰り返す。負閉路の検出も可能。

概念 ── 最適性原理が効く

「最短経路の部分経路もまた最短経路」── これが ベルマンの最適性原理（動的計画法とベルマンの原理）。始点 $s$ から各ノード $v$ への最短距離 $d(v)$ は、隣接ノード経由の最小として再帰的に書ける（ベルマン方程式）：

d(v) = \min_{(u,v) \in E}\ \bigl\{\, d(u) + w(u,v) \,\bigr\}, \qquad d(s) = 0

この再帰をどう解くかで、ダイクストラ（貪欲）とベルマンフォード（反復緩和）に分かれる。

ダイクストラ法（非負辺）

未確定ノードのうち 暫定距離が最小のノードを確定し、その隣接を緩和する、を繰り返す。

graph TD
  A["始点 d(s)=0, 他は∞"] --> B["未確定で最小距離のノード u を確定"]
  B --> C["u の隣接 v を緩和: d(v)=min(d(v), d(u)+w(u,v))"]
  C --> D{"全ノード確定?"}
  D -->|"いいえ"| B
  D -->|"はい"| E["最短距離が確定"]

正当性の鍵は 辺が非負であること：一度確定したノードの距離は、後からより短くなることが無い（遠回りは必ず長くなる）。だから貪欲に確定してよい。負辺があるとこの前提が崩れる。

ベルマンフォード法（負辺対応）

全辺の 緩和（relaxation） $d(v)\leftarrow\min(d(v), d(u)+w(u,v))$ を $V-1$ 回繰り返す。最短経路は高々 $V-1$ 本の辺なので、 $V-1$ 回で全ノードの距離が確定する。さらにもう1回緩和して距離が縮むなら、負閉路が存在する（最短距離が $-\infty$ ）と検出できる。負辺を扱える代わりに $O(VE)$ とダイクストラより遅い。

Pythonで両者を確認

5ノードの有向グラフ（非負辺）で、両手法が同じ最短距離を返すことと、経路復元を見る。

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra, bellman_ford

# 重み付き隣接行列(0は辺なし)。0->1:7, 0->2:9, 1->2:10, 1->3:15, 2->3:11, 3->4:6
graph = np.array([
    [0, 7, 9,  0, 0],
    [0, 0, 10, 15, 0],
    [0, 0, 0, 11, 0],
    [0, 0, 0,  0, 6],
    [0, 0, 0,  0, 0],
], dtype=float)
G = csr_matrix(graph)

dist_d, pred = dijkstra(G, indices=0, return_predecessors=True)
dist_bf = bellman_ford(G, indices=0)
print(f"ダイクストラ  距離 = {dist_d}")
print(f"ベルマンフォード 距離 = {dist_bf}")

# 0->4 の経路を復元
path, i = [4], 4
while i != 0:
    i = int(pred[i]); path.append(i)
print(f"0->4 最短距離={dist_d[4]:.0f}, 経路={list(reversed(path))}")

実行結果：

ダイクストラ  距離 = [ 0.  7.  9. 20. 26.]
ベルマンフォード 距離 = [ 0.  7.  9. 20. 26.]
0->4 最短距離=26, 経路=[0, 2, 3, 4]

両手法とも始点0から各ノードへの最短距離 $[0,7,9,20,26]$ で一致。0→4 の最短経路は $0\to2\to3\to4$ （ $9+11+6=26$ ）で、 $0\to1\to3\to4$ （ $7+15+6=28$ ）より短い。非負辺なのでダイクストラで十分だが、もし負辺があればベルマンフォードが要る。

数式の直観的意味

最短経路はベルマン方程式という 不動点方程式の解。ダイクストラとベルマンフォードは、同じ方程式の異なる解き方：ダイクストラは「確定した距離は二度と変わらない」という単調性（非負辺の帰結）を使って 各ノードを1回ずつ確定する貪欲法。ベルマンフォードは単調性を仮定せず、全辺の緩和を 十分回数繰り返して不動点へ収束させる。緩和操作 $d(v)\leftarrow\min(d(v),d(u)+w)$ は「三角不等式 $d(v)\le d(u)+w(u,v)$ を強制する」操作で、すべての辺で成り立てば最短距離が確定する。最短路 LP は制約行列が全ユニモジュラ（ネットワーク最適化章目次）なので、LP 緩和を解いても自動的に整数（実際の経路）になる ── これがネットワーク問題の「整数なのに易しい」性質。負閉路があると目的が $-\infty$ になり最適解が存在しない（最適化問題とはの非有界）。

⚠️ よくある誤解・落とし穴

ダイクストラは負辺で誤る：負辺があると「確定ノードの距離が後で縮む」ので貪欲が破綻。ベルマンフォードを使う。
負閉路があると最短路は定義されない（無限に回って $-\infty$ ）。ベルマンフォードで検出する。
無向グラフの負辺は実質負閉路：行き来で無限ループ。無向＋負辺は要注意。
全点対最短路なら Floyd–Warshall（ $O(V^3)$ ）、密でない大規模なら各点ダイクストラが速いことも。