最短路問題は出発点の頂点から他の頂点への重みの和が最小の経路を見つける問題 です。ダイクストラ(Dijkstra)という人が考え出した次のアルゴリズム
があります。上のアルゴリズムでは簡単のため最短路の長さd(v)だけ求めていますが、経路(頂点の系列)を出力するように変更するのは容易です。アニメーションでは経路も求めて表示します。
このアルゴリズムの一番大切なところは10行目で、まだ最短路が求まっていない頂点xについて、それまでのd(x)と新たに最短路が求まった頂点uを経由するd(u)+w(u, x)の小さい方を新たなd(x)にしているところです。
これで全ての頂点について最短路が求まることが厳密に証明できます。また、6行目ではd(v)が最小となる頂点を探しますが、ヒープという記憶装置を使うとごく少ない手数で実行できます。どちらも詳しくは教科書などを参照して下さい。ということで、このダイクストラのアルゴリズムは今までに知られている最も効率の良い最短路アルゴリズムです。カーナビなどに使われています。実行の様子は次のリンクから。
