未確定頂点のうち暫定距離が最小の頂点を確定する。辺の緩和を繰り返してより短い経路へ更新するとは？

ダイクストラ法は、始点からの暫定距離が最小の未確定頂点を順に確定し、その頂点から出る辺を用いて隣接頂点の距離を緩和する。辺重みが負でないグラフに適用できる。 ▍なぜ正解 SからBの距離は1、B経由でAは1+2=3、A経由でCは3+1=4となる。さらにCからDへ進むと4+3=7なので、SからDへの最短距離は7である。 ▍よくある間違い 最初に見つけた経路を確定してしまい、B経由でAやCの暫定距離が短縮されることを見落とす。 ▍試験の狙い 各頂点を確定するたびに、隣接頂点の暫定距離が短くなるかを必ず再計算する。