DOSEIの日記

技術メモ+日常ログ

最短経路探索。ダイクストラ法。
V: グラフの点集合

U: 既にチェックした点集合

w(a b): 辺abの重み

l(v): 始点vsから点vまでのこれまでの最短距離

p(v): その1つ前の点∈V

  1. (初期化) l(vs):=0
    ∀i≠s( l(vi):=∞ ), ∀i( p(vi):=∅
    U:={vs}
  2. vsのすべての隣接点vxに対して
    l(vx):=w(vs vx)
    p(vx):=vs
  3. 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
  4. v≠vtならば3へ