Overview
ダイクストラ法（Dijkstra's algorithm） は、辺に非負の重みがあるグラフにおいて、単一の始点から各頂点への最短距離を求めるアルゴリズム。
1.ダイクストラ法の基本
2.ダイクストラ法の注意点
3.典型問題を解いてみる
1. ダイクストラ法の基本
ダイクストラ法（Dijkstra's algorithm） は、辺に非負の重みがあるグラフにおいて、単一の始点から各頂点への最短距離を求めるアルゴリズム。
- 最短経路問題の基本中の基本
- 負の重みがある場合は使用不可（→ ベルマンフォード法を使う）
こんなことに使われている。
| シーン | 活用例 |
|---|---|
| 地図・ナビゲーション | 最短ルート探索（例: Google Maps） |
| ネットワーク通信 | 最小遅延ルート選択 |
| 経路計画・スケジューリング | コストや時間を最小化する計画立案 |
＜アルゴリズムの流れ＞
1.始点の距離を0に、他は∞に初期化
2.優先度付きキュー（min-heap）に (距離, 頂点) を追加
3.キューから取り出す（最も距離が短い頂点）
4.隣接頂点に「距離が短くなるなら更新」し、再びキューに追加
5.全ての頂点についてこれを繰り返す
＜基本実装＞
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
実行例
# 頂点数 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 までの最短距離を求めよ。
回答
上記 dijkstra テンプレートがそのまま使えます。 ```例題2. ABC211 D - Number of Shortest paths
問題:
N 頂点 M 辺の無向グラフが与えられる。頂点 1 から頂点 N への最短経路の本数を求めよ。
回答
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] で更新し、同じ距離の場合は経路数を加算しています。
例題3. ABC168 D - .. (Dot Dot Dot)
問題:
N 頂点 M 辺の無向グラフが与えられる。頂点 1 を始点として、各頂点への最短経路を求め、その経路上で直前の頂点を出力せよ。
回答
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[] 配列に記録し、最短経路の復元に利用しています。