ダイクストラ法（最短経路）
重み付きグラフで、出発点から各地点への 最短距離を、近い地点から順に確定していきます。
0
距離確定ずみ
今回確定する地点
暫定距離あり（未確定）
緩和した辺
各地点への距離（∞＝まだ到達経路が見つかっていない）
辺に「距離（コスト）」がついたグラフで、出発点 S から全地点への最短距離を求めるのが ダイクストラ法です。
考え方：まだ確定していない地点のうち、暫定距離が最小の地点を確定する。確定した地点から伸びる辺を見て、 隣の地点の暫定距離を「より短くできるなら更新」する（＝緩和）。これを全地点が確定するまで繰り返します。
一度確定した距離は二度と変わらない ── これが効率の鍵です（カーナビの経路探索の基礎）。
考え方：まだ確定していない地点のうち、暫定距離が最小の地点を確定する。確定した地点から伸びる辺を見て、 隣の地点の暫定距離を「より短くできるなら更新」する（＝緩和）。これを全地点が確定するまで繰り返します。
一度確定した距離は二度と変わらない ── これが効率の鍵です（カーナビの経路探索の基礎）。
いま何をしている？
ここがポイント
- 毎回 未確定で暫定距離が最小の地点を選んで確定する（貪欲法）。
- 確定した地点から 辺を緩和＝「経由した方が近ければ隣の暫定距離を更新」。
- 確定した距離はもう変わらない ── だから全地点を一度ずつ確定すれば終わり。
- 辺の重みが負だと成り立たない（その場合はベルマンフォード法を使う）。