最短経路問題

連結グラフ G=(V,E) と重み d:E->R+ および 始点 s in V が与えられたとき、 s から 他の頂点までの最短経路と最短距離を求めよ。

ダイクストラ法

ダイクストラ法はたいへん効率の良いアルゴリズムとして知られている。
  1. Set i=0, S0= {u0=s}, L(u0)=0, and L(v)=infinity for v <> u0. If |V| = 1 then stop, otherwise go to step 2.
  2. For each v in V\Si, replace L(v) by min{L(v), L(ui)+dvui}. If L(v) is replaced, put a label (L(v), ui) on v.
  3. Find a vertex v which minimizes {L(v): v in V\Si}, say ui+1 .
  4. Let Si+1 = Si cup {ui+1}.
  5. Replace i by i+1. If i=|V|-1 then stop, otherwise go to step 2.
ダイクストラ法をインプリメントした下のプログラムは O(|V|2) アルゴリズムである。 {v in V\Si : L(v) < infinity} をとっておくために ヒープを用いれば、計算時間を O(|E|log|V|) とすることができる。

JavaScript ソースファイル:

JavaScript デモ:

関連ページ:

Shortest Path Problem

Given a connected graph G=(V,E), a weight d:E->R+ and a fixed vertex s in V, find a shortest path from s to each vertex v in V.

Dijkstra's Algorithm

Dijkstra's algorithm is known to be a good algorithm to find a shortest path.
  1. Set i=0, S0= {u0=s}, L(u0)=0, and L(v)=infinity for v <> u0. If |V| = 1 then stop, otherwise go to step 2.
  2. For each v in V\Si, replace L(v) by min{L(v), L(ui)+dvui}. If L(v) is replaced, put a label (L(v), ui) on v.
  3. Find a vertex v which minimizes {L(v): v in V\Si}, say ui+1.
  4. Let Si+1 = Si cup {ui+1}.
  5. Replace i by i+1. If i=|V|-1 then stop, otherwise go to step 2.
The time required by Dijkstra's algorithm is O(|V|2). It will be reduced to O(|E|log|V|) if heap is used to keep {v in V\Si : L(v) < infinity}.

JavaScript Source File:

JavaScript Demos

See Also