labs.wakayama.ninja
ダイクストラ法
近い頂点から確定し、辺を使って仮距離を更新していく様子を追います。
ダイクストラ法とは
始点からの距離が最も小さい未確定頂点を選び、その頂点から伸びる辺で周囲の仮距離を短くできるか調べます。これを繰り返すと、始点から各頂点への最短距離が決まります。
確定 もう最短距離が変わらない頂点
仮距離 いま分かっている最短候補
前の頂点 経路を復元する手がかり
グラフ
距離表
眺め方
小さい仮距離 の未確定頂点を選ぶところが中心です。
辺をたどって、今の距離より短い経路が見つかったら仮距離と前の頂点を更新します。