《アルゴリズムを学ぶ》26.ダイクストラ法

# Overview
ダイクストラ法（Dijkstra's algorithm） は、辺に非負の重みがあるグラフにおいて、単一の始点から各頂点への最短距離を求めるアルゴリズム。
[1.ダイクストラ法の基本](#1-ダイクストラ法の基本)
[2.ダイクストラ法の注意点](#2-ダイクストラ法の注意点)
[3.典型問題を解いてみる](#3-典型問題を解いてみる)

# 1. ダイクストラ法の基本
ダイクストラ法（Dijkstra's algorithm） は、辺に非負の重みがあるグラフにおいて、単一の始点から各頂点への最短距離を求めるアルゴリズム。
- 最短経路問題の基本中の基本
- 負の重みがある場合は使用不可（→ ベルマンフォード法を使う）

こんなことに使われている。
|シーン	                |活用例                        |
|:----------------------|:----------------------------|
|地図・ナビゲーション      |最短ルート探索（例: Google Maps）|
|ネットワーク通信         |最小遅延ルート選択               |
|経路計画・スケジューリング |コストや時間を最小化する計画立案   |

**＜アルゴリズムの流れ＞**
1.始点の距離を0に、他は∞に初期化
2.優先度付きキュー（min-heap）に (距離, 頂点) を追加
3.キューから取り出す（最も距離が短い頂点）
4.隣接頂点に「距離が短くなるなら更新」し、再びキューに追加
5.全ての頂点についてこれを繰り返す


**＜基本実装＞**
```python
import heapq

def dijkstra(N, graph, start):
    INF = float('inf')
    dist = [INF] * N
    dist[start] = 0
    hq = [(0, start)]  # (距離, 頂点)

    while hq:
        d, v = heapq.heappop(hq)
        if d > dist[v]:
            continue  # より短い経路が既にある

        for to, cost in graph[v]:
            if dist[to] > dist[v] + cost:
                dist[to] = dist[v] + cost
                heapq.heappush(hq, (dist[to], to))

    return dist
```
実行例
```Python
# 頂点数 N, 辺数 M
N, M = map(int, input().split())
graph = [[] for _ in range(N)]

for _ in range(M):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))  # 有向グラフ（無向なら v→u も追加）

start = 0  # 始点
dist = dijkstra(N, graph, start)

# 各頂点への最短距離を出力
for d in dist:
    print(d if d != float('inf') else "INF")
```

# 2. ダイクストラ法の注意点
|注意点	|解説
|:----------------------|:----------------------------|
|負の重みがあると不正確になる	|ダイクストラ法は負の辺に対応していない（→ベルマンフォード法を使う）
|距離更新時に条件判定を忘れない	|`if dist[to] > dist[v] + cost:` を入れないと誤動作
|訪問済み管理が不要な場合もある	|`dist[]`で距離が小さいものだけ更新すれば良い

# 3. 典型問題を解いてみる

### 例題1. 最短経路（基本）
**問題:
N 頂点 M 辺の有向グラフが与えられる。頂点 1 から N までの最短距離を求めよ。**

> [参考： ABC254 D - Shortest Path](https://atcoder.jp/contests/abc254/tasks/abc254_d)
<details><summary> 回答　</summary>
上記 dijkstra テンプレートがそのまま使えます。
```
</details>

### 例題2. ABC211 D - Number of Shortest paths
**問題:
N 頂点 M 辺の無向グラフが与えられる。頂点 1 から頂点 N への最短経路の本数を求めよ。**

> [参考： ABC211 D - Number of Shortest paths](https://atcoder.jp/contests/abc211/tasks/abc211_d)

<details><summary> 回答　</summary>

```python
import heapq

def dijkstra_count_paths(N, graph, start):
    INF = float('inf')
    dist = [INF] * N
    count = [0] * N
    dist[start] = 0
    count[start] = 1
    hq = [(0, start)]  # (距離, 頂点)

    while hq:
        d, v = heapq.heappop(hq)
        if d > dist[v]:
            continue

        for to in graph[v]:
            if dist[to] > dist[v] + 1:
                dist[to] = dist[v] + 1
                count[to] = count[v]
                heapq.heappush(hq, (dist[to], to))
            elif dist[to] == dist[v] + 1:
                count[to] += count[v]

    return dist, count

# 入力の読み込み
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(lambda x: int(x)-1, input().split())
    graph[u].append(v)
    graph[v].append(u)

dist, count = dijkstra_count_paths(N, graph, 0)
print(count[N-1] % (10**9 + 7))
```

ポイント:
- 通常のダイクストラ法に加えて、最短経路の本数を数えるための count[] 配列を追加しています。
- 最短距離が更新された場合、count[to] を count[v] で更新し、同じ距離の場合は経路数を加算しています。
</details>

### 例題3. ABC168 D - .. (Dot Dot Dot)
**問題:
N 頂点 M 辺の無向グラフが与えられる。頂点 1 を始点として、各頂点への最短経路を求め、その経路上で直前の頂点を出力せよ。**

> [参考： ABC168 D - .. (Dot Dot Dot)](https://atcoder.jp/contests/abc168/tasks/abc168_d)

<details><summary> 回答　</summary>

```python
from collections import deque

def bfs_shortest_path(N, graph, start):
    dist = [-1] * N
    prev = [-1] * N
    dist[start] = 0
    queue = deque([start])

    while queue:
        v = queue.popleft()
        for to in graph[v]:
            if dist[to] == -1:
                dist[to] = dist[v] + 1
                prev[to] = v
                queue.append(to)

    return prev

# 入力の読み込み
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(lambda x: int(x)-1, input().split())
    graph[u].append(v)
    graph[v].append(u)

prev = bfs_shortest_path(N, graph, 0)

print("Yes")
for i in range(1, N):
    print(prev[i] + 1)
```

ポイント:
- 無向グラフかつ全ての辺の重みが等しい場合、BFS（幅優先探索）で最短経路を求めることができます。
- 各頂点に到達する直前の頂点を prev[] 配列に記録し、最短経路の復元に利用しています。
</details>