読者です 読者をやめる 読者になる 読者になる

Dijkstraのアルゴリズム

入力:有向グラフG, 非負の重み関数 c: E(G) → R_+ および始点 s ∈ V(G)
出力:sからすべての点 v ∈ V(G) への最短パスとその距離、より正確には、
   すべての点 v ∈ V(G) に対する p(v) と l(v) ただし、l(v) は最短s-p(v)-パスと
   辺(p(v), v)からなる最短s-v-パスの長さである。vがsから到達不可能なときは
   l(v) = ∞ であり、p(v) は未定義

l(s) := 0, ∀v ∈ V(G)\{s} で l(v) := ∞, R := 0 と初期化する
l(v) = min (w ∈ V(G))\R l(w)となる点 v ∈ V(G)\R を求める
R := R∪{v} とする
For(v,w) ∈ E(G) を満たすすべての w ∈V(G)\R do:
    If l(w) > l(v) + c( (v,w) ) then
        l(w) := l(v) + c( (v,w) ), p(w) := v とする
If R≠V(G) then goto 2行目