最短経路 — ダイクストラとA*、そして負の辺

道ごとに距離も混雑も違う現実の地図では、「歩数が少ない＝速い」は成り立ちません。枝に重み（コスト）がつく世界で、本当の最短経路を求める。距離ラベルを賢く伸ばすダイクストラ法、ゴールへ当たりをつけて掘るA*、そして負の辺がなぜダイクストラを壊すのか（＝ベルマンフォードの出番）まで、動かして掴みます。

1. 重み付きグラフ — 「歩数最小」と「コスト最小」は違う

前章の BFS は、すべての移動が「1歩」で等しいときに最短でした。でも地図では、平地は軽く・山や渋滞は重い。各マスに通行コスト（重み）を与えると、歩数が最も少ない道と、合計コストが最も小さい道は別物になります。

下の図で、水色＝歩数最小（BFS）と オレンジ＝コスト最小（ダイクストラ）の2本を見比べてください。マスの数字が通行コスト、地の色は緑＝軽い／赤＝重い。しばしば、遠回りに見えるオレンジのほうが合計コストは小さいのです。

重みが道を変える — 歩数最小 vs コスト最小
各マスの数字＝そのマスに入るコスト。地の色は緑（軽い）→赤（重い）。水色は歩数だけで選んだ道、オレンジはコスト合計を最小にした道。険しさを上げるほど、両者が食い違い、コスト最小が「重い山を避けて回り込む」のが見えてきます。
POINT — 最短とは「重みの合計」が最小 重み付きグラフでの最短経路は、通った枝の重みの総和が最小の道。BFS は重みを見ずに歩数だけ数えるので、重みがあると最短を外す。だから「暫定距離を、より短い経路が見つかるたびに更新（緩和）する」という新しい考え方が要る。それがダイクストラ法です。

2. ダイクストラ法 — 距離ラベルが染み出す

ダイクストラ法の心臓は2つの操作です。①緩和（relax）：あるマスから隣へ「今より短く行けるなら暫定距離を書き換える」。②確定：まだ確定していないマスの中で暫定距離が最小のものを選び、その値を最短として確定する（＝優先度つきキュー）。

確定したマスからは二度と値が下がらない、という保証（重みが非負なら成立）が効率の源。再生して、暫定距離の数字がスタートからじわじわ外へ染み出し、最小のマスが次々に確定していき、最後にゴールから最短経路が逆にたどれる様子を見てください。

ダイクストラ — 暫定距離が広がり、最小から確定する
数字＝スタートからの暫定距離（＝そこまでの最小コスト）。青＝確定済み、オレンジ縁＝発見済みで未確定（優先度キューの中身）。白枠＝いま確定する「暫定距離が最小のマス」。ゴール確定でオレンジの最短経路が光ります。青がほぼ円形に広がるのがダイクストラの個性です。
緩和：dist[v] ← min( dist[v],　dist[u] + w(u→v) ) u から v へ「今より短い道」が見つかれば書き換える。これを、暫定最小のマスから順に繰り返すだけ

3. A* — ゴールへ当たりをつけて掘る

ダイクストラは全方位に平等に広がるので、ゴールと反対側まで無駄に調べます。そこでA*（エースター）は、各マスの評価に「ゴールまでの推定残り距離」＝ヒューリスティック h を足します。確定する順番を f ＝ 距離 g ＋ 推定 h の小さい順にすると、探索がゴールの方向へ細長い扇（コーン）になり、調べるマスがぐっと減ります。

下は同じ地形での競走。左のダイクストラは円、右の A* はゴールへ向かう扇。h が本当の距離を超えなければ（＝許容的なら）、A* もダイクストラと同じ最短経路にたどり着きます — より少ない手間で。

ダイクストラ（円）vs A*（ゴールへ向かう扇）
両者を1手ずつ同時に。下のカウンタで確定マス数を比べると、A*（右）のほうが少ないのが分かります。ヒューリスティック（マンハッタン距離）がゴール方向へ探索を引っぱるからです。最終的な経路コストは両者で同じ＝どちらも本当の最短。
POINT — h が「甘め」なら最適、「盛りすぎ」なら速いが不正確 A* のヒューリスティック h が実際の残り距離を決して超えない（許容的 / admissible）なら、見つかる経路は必ず最短。h＝0 にすればダイクストラそのもの。逆に h を過大にすると探索は速くなるが最短の保証を失う（重み付きA*）。h の設計が A* の賢さと正しさを両立させる鍵です。

4. 負の辺という落とし穴 — そしてベルマンフォード（まとめ）

ダイクストラの効率は「一度確定したマスは二度と短くならない」という前提に支えられています。ところが負の重みの辺があると、この前提が崩れます。あとから負の辺を通ると、確定済みのマスがさらに短くなり得るのに、ダイクストラは覆せず誤った答えを出します。

下の小さなグラフで確かめましょう。ダイクストラは B を距離2で早々に確定しますが、実は S→A→B ＝ 3＋(−3) ＝ 0 が正解。この誤りを直すのが、確定せずに全ての辺を |V|−1 回くり返し緩和するベルマンフォード法です。

負の辺で崩れるダイクストラ／直すベルマンフォード
辺の数字＝重み（A→B は −3 の負の辺）。ダイクストラは B を 2 で確定してしまい、あとから来る近道（S→A→B＝0）を反映できず誤答。ベルマンフォードは全辺を2回なめ直して 0＝正解にたどり着きます。再生で自動進行、「次のステップ」で1手ずつ。
ダイクストラ O((V+E) log V)　／　ベルマンフォード O(V · E) 負の辺があるならベルマンフォード（負の閉路検出も可）。無いならダイクストラが速い。A* はダイクストラ＋ヒューリスティックで実質さらに速い
一歩先へ — カーナビと、その先へ 実際のカーナビは、全国の道路を毎回ダイクストラで解いていては間に合わない。階層化（高速道路を上位ネットワークとして先に解く）や、事前計算で枝を刈るContraction Hierarchies などで、大陸規模の地図をミリ秒で解く。基礎はすべて、ここで見た「緩和と確定」。この考えは第8章の探索と地続きで、経路計画（自動運転のA*）やゲームAIへと広がっていきます。