最短経路問題 ― 重み付きグラフを探索する
BFS最短路，Dijkstraの正当性証明，Bellman-Ford，負閉路検出，Warshall-Floyd，DAG上の最短路を体系的に扱う．
1 最短経路問題の定式化
定義 1 (重み付きグラフと経路の重み).
重み付きグラフ とは，グラフ と重み関数 の組である．経路 に対して， の重み（または長さ）を
と定める．
定義 2 (最短経路と最短距離).
頂点 から への経路全体を とする．最短距離を
と定める． を満たす経路 を最短経路（shortest path）という．
注意 3.
負の重みを持つ閉路（負閉路）が到達可能であれば，その閉路を何周もすることで経路の重みをいくらでも小さくでき，最短経路は存在しない．この場合を と定義する．
2 BFS最短路：重みなしの場合
すべての辺の重みがのとき，BFS（幅優先探索）が最短距離を正しく計算する．
定理 4 (BFS の正当性).
重みなしグラフ において，始点 から BFS を実行し を が発見された層とする．このとき任意の に対して が成り立つ．
証明.
とし，帰納法で示す． のとき であり なので成立． とし， のすべての頂点で成立を仮定する． から への最短路 を取る． であるから帰納法の仮定より である．BFS は を処理する際に を（未訪問なら）キューに追加するので となる．一方 であれば となって矛盾する（BFS は各辺をちょうど ステップで辿るため， 以下の距離の経路が存在することになる）．よって ． □
BFS の計算量はである．
アルゴリズム 1: 幅優先探索 (BFS)
Input:
グラフ ，始点 Output:
各頂点の最短距離 for all
end for
キュー
Enqueue()
while
for all
if
Enqueue()
end if
end for
end while
return
3 Dijkstra のアルゴリズム
辺の重みが非負の場合に，単一始点最短路を効率的に求める手法が Dijkstra のアルゴリズムである．
アルゴリズムの骨子は次の通りである：確定済み集合を管理し，に属さない頂点のうち暫定距離が最小のものを選んでに追加し，その頂点から出る辺で緩和（relaxation）を行う．
定義 5 (緩和).
辺 に対する緩和とは， ならば と更新する操作をいう．
定理 6 (Dijkstra の正当性).
辺の重みがすべて非負であるグラフにおいて，Dijkstra のアルゴリズムは各頂点 に対して を正しく計算する．
証明.
に追加される頂点 に対して であることを， に追加される順に帰納法で示す．基底： が最初に追加され である．帰納段階： に新たに追加される頂点を とする． と仮定して矛盾を導く． から への最短路 を取り， 上で を初めて出る辺 （，）を考える．帰納法の仮定より である． を に追加した時点で辺 を緩和しているので，
一方， より である（ は 上で 以前）．よって であるが， は 外で が最小の頂点として選ばれたので であり矛盾． □
アルゴリズム 2: Dijkstra のアルゴリズム
Input:
グラフ ，非負重み ，始点 Output:
各頂点の最短距離 for all
end for
優先度付きキュー に全頂点を 値で挿入
while
for all
if
DecreaseKey()
end if
end for
end while
return
注意 7.
二分ヒープを用いた実装では計算量は ，フィボナッチヒープでは となる．
4 Bellman-Ford アルゴリズム
辺の重みに負が含まれる場合，Dijkstra は正しく動作しない．Bellman-Ford アルゴリズムは負の辺重みを許容し，さらに負閉路の検出も可能である．
アルゴリズムはすべての辺に対する緩和を回繰り返す．
定理 8 (Bellman-Ford の正当性).
負閉路が存在しないグラフにおいて， 回の反復後，すべての頂点 に対して が成り立つ．
証明.
最短路は（負閉路がなければ）高々 本の辺からなる． から への最短路を （）とする． 回目の反復後に が成り立つことを に関する帰納法で示す． は で成立． のとき，帰納法の仮定より 回目の反復後に である． 回目の反復で辺 を緩和するので，
は緩和の性質から常に成り立つので等号が成立する． □
定理 9 (負閉路の検出).
Bellman-Ford の 回の反復後にさらに 回すべての辺を緩和して， が更新される頂点 が存在すれば， から到達可能な負閉路が存在する．
証明.
負閉路がなければ 回目で全頂点の 値が確定し，追加の緩和で更新は起きない．対偶より，更新が起きれば負閉路が存在する． □
Bellman-Ford の計算量はである．
アルゴリズム 3: Bellman-Ford アルゴリズム
Input:
有向グラフ ，重み ，始点 Output:
各頂点の最短距離 ，負閉路の有無 for all
end for
for to
for all
if
end if
end for
end for
// 負閉路の検出
for all
if
return 「負閉路が存在する」
end if
end for
return
5 Warshall-Floyd アルゴリズム
全頂点対間の最短距離を動的計画法で求める手法が Warshall-Floyd アルゴリズムである．
定理 10 (Warshall-Floyd の漸化式).
とし， を中間頂点として のみを使う から への最短距離とする．このとき
が成り立ち， である．
証明.
頂点 を中間頂点として使わない最短路の重みは に等しい．頂点 を使う場合，最短路は と分解でき（負閉路がなければ は最短路上に高々 回出現），その重みは である．両者の最小値が を与える． □
アルゴリズム 4: Warshall-Floyd アルゴリズム
Input:
有向グラフ ，重み ， Output:
全頂点対間の最短距離 for to
for to
if
else if
else
end if
end for
end for
for to
for to
for to
end for
end for
end for
return
計算量はであり，対角成分であれば頂点を含む負閉路が存在する．
6 DAG 上の最短路
定理 11 (DAG 上の線形時間最短路).
DAG（有向非巡回グラフ）上の単一始点最短路は，頂点をトポロジカル順序で並べ，その順に各辺を 回ずつ緩和するだけで で計算できる．
証明.
トポロジカル順序では，辺 があれば が より前に現れる．したがって頂点 を処理する時点で， に入る辺 の始点 はすべて処理済みであり が確定している．よって辺 の緩和により が正しく得られる． □
注意 12.
DAG 上の最短路は辺の重みに負があっても正しく動作する．閉路がないため負閉路の心配がないからである．この手法は PERT（Program Evaluation and Review Technique）など，プロジェクト管理における最長路（クリティカルパス）の計算にも応用される．