最短路問題は出発点の頂点から他の頂点への重みの和が最小の経路を見つける問題 です。ダイクストラ(Dijkstra)という人が考え出した次のアルゴリズム ダイクストラのアルゴリズム があります。上のアルゴリズムでは簡単のため最短路の長さd(v)だけ求めていますが、経路(頂点の系列)を出力するように変更するのは容易です。アニメーションでは経路も求めて表示します。 このアルゴリズムの一番大切なところは10行目で、まだ最短路が求まっていない頂点xについて、それまでのd(x)と新たに最短路が求まった頂点uを経由するd(u)+w(u, x)の小さい方を新たなd(x)にしているところです。 最短距離の更新 …
naoya-2.hatenadiary.org
blog.unfindable.net
ygussany.hatenablog.com
theorist.blog6.fc2.com