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

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つの都市を結ぶ道路があります。

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. 擬似コード

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)

まとめ

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