■
最短経路探索。ダイクストラ法。
V: グラフの点集合
U: 既にチェックした点集合
w(a b): 辺abの重み
l(v): 始点vsから点vまでのこれまでの最短距離
p(v): その1つ前の点∈V
- (初期化) l(vs):=0
∀i≠s( l(vi):=∞ ), ∀i( p(vi):=∅
U:={vs} - vsのすべての隣接点vxに対して
l(vx):=w(vs vx)
p(vx):=vs - V\Uのl(v)が最小となるvについて
∀vy∈V\U( l(vy):=min{l(vy) l(v)+w(v vy)} )
U:=U∪{v}
もしl(vy)=l(v)+w(v vy)ならば(つまり更新されたら)p(vy):=v - v≠vtならば3へ