markdown
ダイクストラ法の基本
lecture/information/algorithm/graph/ダイクストラ法の基本-講義.n.md
ダイクストラ法の基本
algorithmgraphundergraduatelecture
導入
この講義で最重要なのは、ダイクストラ法は「いま一番近い未確定の頂点から順に距離を確定していく」方法だということです。
重みつき最短路では、ただ幅優先に広げるだけでは足りません。しかし辺の重みが負でなければ、いま最小の距離をもつ候補を確定しても、あとからもっと短い道が出てくることはありません。この事実を使うのがダイクストラ法です。
用語と定義
確定 とは、その頂点までの最短距離がもう変わらないと認めることです。
更新 とは、ある辺を通った方が距離を短くできるなら、記録を書き換えることです。
方針
まず始点の距離を 0、他を無限大として始めます。そのあと、未確定の頂点のうち距離が最小のものを選んで確定し、そこから出る辺で更新を行います。
直感的な説明
地図で近い町から順に「ここまではもう最短で着ける」と印をつけていく感覚です。重みが負でなければ、いま一番近い町を後回しにする理由はありません。
厳密な説明
1. 初期化
始点 s に対して
\mathrm{dist}(s)=0
とし、他の頂点は
\mathrm{dist}(v)=\infty
とします。
2. 確定
未確定の頂点のうち、\mathrm{dist} が最小のもの u を選びます。辺の重みが負でないので、u より短い道があとから現れることはありません。したがって u を確定できます。
3. 更新
u から隣接する頂点 v に重み w(u,v) の辺があるとき、
\mathrm{dist}(u)+w(u,v)<\mathrm{dist}(v)
なら
\mathrm{dist}(v)\leftarrow \mathrm{dist}(u)+w(u,v)
と更新します。
見分け方
- 重みつき最短路で、重みが負でないならダイクストラ法の候補です。
- 最小の距離をもつ未確定の頂点を順に確定していく、という言葉で説明できるかを確認します。
- 負の重みがあると、この「いま最小なら確定してよい」という理屈が壊れます。
最終形
\boxed{\text{負でない重みつき最短路} \Rightarrow \text{ダイクストラ法}}
\boxed{\text{最小の未確定頂点を選び, 更新を繰り返す}}
一言でいうと
- ダイクストラ法は、負でない重みつきグラフで、近い頂点から順に最短距離を確定していく手法です。