最短経路問題（ダイクストラ法）

📌

最短経路問題とは

最短経路問題（Shortest Path Problem）とは、辺に重み（距離やコスト）がついたグラフ上で、ある2点を結ぶ経路のうち重みの合計が最小になる道を見つける問題です。「最も距離が短い」だけでなく「最も料金が安い」「最も時間がかからない」なども同じ枠組みで扱えます。

身近な例で言うと、カーナビがまさにこれです。出発地から目的地まで、無数にある道順の中から「一番早く着くルート」を計算してくれます。直線距離が短くても渋滞で遠回りになることがあるように、最短経路は「見た目の近さ」ではなく「重みの合計」で決まります。

上のツールで▶ボタンを押すと、スタート S からゴール G までの最短距離を求める過程が1.5秒ごとに進みます。各ノードに表示される数字が「そこへ行くのに必要な最小コスト」です。

🧭

ダイクストラ法の手順

ダイクストラ法は、最短経路を効率よく求める代表的なアルゴリズムです。「今いちばん近いと分かっている点」から順に確定させていく、欲張りな（貪欲な）手順で進みます。

手順は次の通りです。
・① 初期化：スタートの距離を 0、他をすべて ∞ にする
・② 最小を確定：未確定の中で暫定距離が最小のノードを選び、最短距離として確定する
・③ 隣を更新（緩和）：確定したノードを経由した方が近い隣接ノードの暫定距離を書き換える
・④ 繰り返す：すべてのノードが確定するまで②③を繰り返す

③の緩和（リラクゼーション）とは、「確定済みの距離 + 辺の重み」が今の暫定距離より小さければ更新する操作です。たとえば S→A が 2、A→B が 1 なら、B へは S→B 直行（5）よりも S→A→B（3）の方が近い、と書き換えます。重要なのは一度確定した距離は二度と変わらない点です。

🛠️

用途(カーナビ・ネットワーク等)

最短経路の計算は、私たちの生活やITインフラの至るところで使われています。代表的な用途を挙げます。
・カーナビ・地図アプリ：道路網を重み付きグラフとみなし、最短時間ルートを案内
・ネットワークのルーティング：データを最小コストの経路で目的地へ届ける（OSPFなどのルーティングプロトコル）
・物流・配送計画：倉庫から各拠点へ最も効率よく荷物を運ぶ経路の決定

身近な例では、乗換案内アプリが分かりやすいです。駅をノード、路線を辺、所要時間や運賃を重みと考えれば、「最も早い乗換」「最も安い乗換」はどちらも最短経路問題として解けます。重みを「時間」にするか「料金」にするかで答えが変わるのが面白いところです。

重要な性質として、ダイクストラ法は辺の重みがすべて 0 以上のときにだけ正しく動く点を押さえておきましょう。マイナスの重み（割引で距離が減るような辺）がある場合は、ベルマン・フォード法など別のアルゴリズムを使う必要があります。

📌

グラフ・ノード・辺・重みって何？

最短経路の話に出てくる「グラフ」とは、「点と線でものごとのつながりを表した図」のことです。難しい数学の話ではなく、路線図や友達関係の図と同じ考え方です。

グラフを作る3つの要素を整理しましょう。
・ノード（＝頂点・点）：駅や交差点など「場所」を表す丸。上の図では A・B・C がノードです
・辺（＝エッジ・線）：ノードとノードをつなぐ道。「A と B はつながっている」を表します
・重み（＝コスト）：辺についている数値。距離・時間・料金など「その道を使うコスト」を表します

電車の路線図で考えると分かりやすいです。各駅がノード、路線（線路）が辺、各区間の所要時間が重みです。最短経路問題は「A駅から G 駅まで、重みの合計（所要時間の合計）が最小になるルートはどれか」を求めることに当たります。上の図でも、A→B（重み3）と A→C（重み7）では、B のほうが A からの「コスト」が低いと一目で分かります。

📌

なぜ「最小を選べば必ず正解」なのか

結論: 重みが 0 以上のグラフでは、「今いちばん小さい暫定距離のノード」はもう二度と更新されません。だから安全に「確定」できます。

なぜそう言えるのか。上の図で考えましょう。S から A への距離が 2、S から B への距離が 5 だとします。A の 2 より小さい値に後から更新できるでしょうか？

更新するには「別のノードを経由して A に到達する道」が必要です。しかしどの辺の重みも 0 以上なので、B（dist=5）を経由すると少なくとも 5 以上のコストがかかります。5 は 2 より大きいので、B を経由しても A の暫定距離 2 を下回ることは絶対にありません。
・重みが 0 以上なら、迂回すればするほどコストは増えるだけ
・だから最小の暫定距離のノードは「これより短い道は存在しない」と言い切れる
・これが「貪欲（最小を選び続ける）戦略が正しく動く」理由です

身近なアナロジーで言うと、「すでに財布に入っているお金は増えない」状況に似ています。今持っているお金（暫定距離）より多く使わないと次の場所に行けないなら、今の最安地点が最安のままです。もしマイナスの重み（「通ると距離が減る近道」）があればこの保証が崩れるため、ダイクストラ法は使えなくなります。