====== ダイクストラ法を理解しよう ======

=== 1. なぜダイクストラ法が必要？ ===
DFSやBFSは「行けるかどうか」を調べる探索です。しかし、道に「重み（コスト）」がある場合、最短距離を求めるには別の方法が必要です。そこで登場するのが **ダイクストラ法** です。

  * DFS → 深さ優先探索（順番に深く進む）
  * BFS → 幅優先探索（近い順に進む）
  * ダイクストラ法 → 「重み付きグラフ」で最短経路を求める

=== 2. 接続リスト（表に基づく） ===
  * A → B (2), A → C (5)
  * B → C (1), B → D (4)
  * C → D (1), C → E (3)
  * D → E (2)

5つの都市を結ぶ道路があります。

|< 300px 50px 50px 50px 50px 50px 50px >|
^   Node  ^  A  ^  B  ^  C  ^  D  ^  E  ^
|  A  |  -  |  2  |  5  |  -  |  -  |
|  B  |  2  |  -  |  1  |  4  |  -  |
|  C  |  5  |  1  |  -  |  1  |  3  |
|  D  |  -  |  4  |  1  |  -  |  2  |
|  E  |  -  |  -  |  3  |  2  |  -  |

スタート：A
ゴール：E

=== 3. アルゴリズムの基本アイデア ===
  * 各地点までの「最短距離」をメモする
  * スタートから近い順に「確定」していく
  * 未確定の中で一番近いものを選び、距離を更新する

=== 4. 例題と手順（更新理由付き） ===
スタート：A
ゴール：E

初期状態：
  * A=0, B=∞, C=∞, D=∞, E=∞

==== 手順詳細 ====
1. A確定（距離0）
  * B=2に更新（A→Bのコスト2）
  * C=5に更新（A→Cのコスト5）
  * 状態：A=0(確定), B=2, C=5, D=∞, E=∞

2. B確定（距離2）
  * C=3に更新（A→B→Cで2+1=3、以前の5より小さい）
  * D=6に更新（A→B→Dで2+4=6）
  * 状態：A=0, B=2(確定), C=3, D=6, E=∞

3. C確定（距離3）
  * D=4に更新（A→B→C→Dで3+1=4、以前の6より小さい）
  * E=6に更新（A→B→C→Eで3+3=6）
  * 状態：A=0, B=2, C=3(確定), D=4, E=6

4. D確定（距離4）
  * E=6（更新なし、4+2=6で同じ）
  * 状態：A=0, B=2, C=3, D=4(確定), E=6

5. E確定（距離6）
  * 完了

最短距離：A→B→C→D→E = 6

=== 5. 擬似コード ===
<code>
function dijkstra(graph, start):
    dist[] = ∞
    dist[start] = 0
    visited[] = false

    while 未確定ノードがある:
        u = 未確定で最小distのノード
        visited[u] = true
        for v in uの隣接ノード:
            if dist[v] > dist[u] + cost(u,v):
                dist[v] = dist[u] + cost(u,v)
</code>

=== まとめ ===
  * ダイクストラ法は「重み付きグラフの最短経路」を求める
  * BFSは重みが全部同じなら最短経路になる