ALGO_SPEC: ダイクストラ法

新人エンジニアが学ぶべき、最短経路探索の王道アルゴリズムです。カーナビゲーションシステムやネットワークルーティング（OSPFなど）の強固な土台となっています。

1. コストの「緩和 (Relaxation)」

スタート地点からの距離（コスト）を最初は「無限大（infty）」としておき、より短いルートが見つかるたびに値を更新していく処理を「緩和」と呼びます。このゲームでも、緑色に繋がっていくたびに内部でコストが緩和されています。

2. 貪欲な選択 (Greedy Approach)

常に「現時点で最もコストが小さい未確定ノード」を次々に確定させていくアプローチを取ります。なお、負のコスト（マイナスの距離）を持つエッジが存在しない場合にのみ、正しい結果が保証されます。

3. データ構造と計算量

探索するノードを選ぶ際、単純な配列を使うと計算量は O(V^2) となりますが、優先度付きキュー（Min-Heap）を使うことで、計算量を O((V+E) log V) に劇的に抑えることができます（V は頂点数、E は辺数）。

4. 実務での視点

実用的なAIやゲームの経路探索では、ダイクストラ法に「ゴールへの方向（ヒューリスティック関数）」を加えた A* (A-star) アルゴリズム が多用されます。ダイクストラ法はその母体として必須の知識です。

最短経路探索ゲーム（ダイクストラ法）

スタート(A)からゴール(F)まで最短ルートを構築せよ。通過した地点はすべてグリーンに点灯します。

現在位置: A
移動コスト合計: 0
目標: F駅

アルゴリズム学習：ダイクストラ法

最短経路を見つけるために、コンピュータは探索した地点を「確定済み」としてマークしていきます。

1. 探索の可視化: このゲームでは、あなたが訪れたノードはすべてネオングリーンに統一されます。これはアルゴリズムがその地点を最短経路の候補として確定させた状態を表しています。
2. コスト計算: 各線にある数値を足し、ゴールした瞬間にコンピュータが計算した絶対的な最短値と比較します。