ダイクストラ法

概要

ダイクストラ法(Dijkstra's Algorithm)は，始点（出発点）の指定された重み付きグラフを入力することで，始点から他の全ての点への最短距離とその経路を出力する効率的なアルゴリズムである．ただし，負の重みが存在する場合は解が正しく出力されないことがある．探索においては，頂点を始点からの距離が小さい順に見つけ出してゆく．

なお，グラフは始点を除くどの頂点も始点から到達可能であるとし，コストは全て正であるとする．

アルゴリズム

$\mathrm{dist}(v_i)$を始点から$v_i$への（暫定）距離，$\mathrm{cost}(e_{ij})$を$e_{ij}$のコスト（重み）とする．

入力

頂点の集合$V$
辺の集合$E$（重みの情報も含む）
始点$v_0\in V$

出力

各頂点の始点からの距離
各頂点の直前の頂点

STEP1　グラフの初期化

始点$v_0$の始点からの距離$\mathrm{dist}(v_0)=0$とし，他の頂点の距離は$\infty$（無限大）とする．
また，すべての頂点の直前の点を無し（null）とし，距離未確定の頂点$Q:=V$とする．
（$:=$はここでは「右辺を左辺に代入する」くらいの意味）

STEP2　距離の更新の反復

（最初は$i=0$からスタートする）
$Q:=Q\backslash v_i\ $とする（$Q$から$v_i$を除く）．$v_i$から出ている辺を順番にすべて検討してゆく．$e_{ij}$および$v_j$について，
\begin{equation} \mathrm{dist}(v_i)+\mathrm{cost}(e_{ij})\lt \mathrm{dist}(v_j) \end{equation} なら \begin{equation} \mathrm{dist}(v_j):=\mathrm{dist}(v_i)+\mathrm{cost}(e_{ij}) \end{equation} とし，$v_j$の直前の点を$v_i$とする．（更新）

そうでなければ$\mathrm{dist}(v_j)$および$v_j$の直前の頂点は更新しない．


$v_i$からから出ているすべての辺についての検討を終えたら，$v_i$を$Q$の中で距離が最小である頂点としSTEP2を反復する．$Q=\emptyset$（空集合）となったらSTEP3へ進む．

STEP3　終了

探索を終了し，すべての頂点の距離のリストおよびすべての頂点の直前の頂点のリストを出力する．