グラフ理論において最短経路を求める基本中の基本が「ダイクストラ法（Dijkstra’s Algorithm）」です。この記事では、ダイクストラ法の仕組み・使い方・Pythonでの実装例を初心者にもわかりやすく解説します！
ダイクストラ法とは？
ダイクストラ法は、1959年にオランダの計算機科学者エドガー・ダイクストラによって発表された、重み付きグラフにおける最短経路探索アルゴリズムです。
特徴
- 負の重みを持たないグラフで使用可能
- 始点から各頂点への最短経路を一括で求められる
- 無向グラフ・有向グラフどちらでも対応可能
- **貪欲法（Greedy Algorithm）**に基づいている
どんなときに使うのか？
- Googleマップなどのルート検索アプリ
- ネットワークの最短経路計算（パケットの送信経路）
- ゲームAIの移動経路の計算
- 経路最適化が必要な業務システム
ダイクストラ法の動作の流れ（わかりやすく解説）
1. 初期化
- 始点の距離を0に、それ以外を「∞（無限大）」とする
- 訪問済みフラグを持たせて管理する
2. 最も距離が短い未訪問ノードを選ぶ
3. 隣接ノードの距離を「今の距離 + 移動コスト」で計算
→ 現在記録している距離より短ければ更新（これを緩和処理という）
4. 上記をすべてのノードに対して繰り返す
実例でイメージしてみよう（図解）
以下のようなグラフがあるとします。
A --1-- B --2-- C
| |
4 5
| |
D-------E
Aから各ノードへの最短経路は？
- A → B：1
- A → C：1 + 2 = 3
- A → D：4
- A → E：4 + 1 = 5
このように、ノード間の距離とコストに基づいて、最も効率的なルートを求めるのがダイクストラ法です。
Pythonでの実装方法（初心者向け）
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
queue = [(0, start)] # (距離, ノード)
while queue:
current_distance, current_node = heapq.heappop(queue)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(queue, (distance, neighbor))
return distances
# グラフ定義（隣接リスト形式）
graph = {
'A': [('B', 1), ('D', 4)],
'B': [('A', 1), ('C', 2), ('E', 5)],
'C': [('B', 2)],
'D': [('A', 4), ('E', 1)],
'E': [('B', 5), ('D', 1)],
}
# 実行例
print(dijkstra(graph, 'A'))
時間計算量と注意点
| 実装方法 | 時間計算量 |
|---|---|
| 配列＋線形探索 | O(V²) |
| 優先度付きキュー（heapq） | O((V + E) log V) ※推奨 |
※V: 頂点数、E: 辺の数
よくある質問
Q. 「負の重み」があるグラフには使えますか？
A. 使えません。→その場合はベルマンフォード法またはワーシャルフロイド法を使用しましょう。
Q. 最短経路そのもの（通った経路）も知りたい場合は？
A. 各ノードに対して「前のノード」を記録しておくことで、後から復元可能です。
ダイクストラ法に関連する他のアルゴリズムも学ぼう！
| アルゴリズム | 特徴 |
|---|---|
| ベルマンフォード法 | 負の重みOK。負の閉路がある場合は検出可能 |
| ワーシャルフロイド法 | 全点対間の最短経路を一括計算可能 |
| A*アルゴリズム | ヒューリスティックを加えた最短経路探索 |
ダイクストラ法まとめ
- 始点から各ノードへの最短距離を求める定番アルゴリズム
- 負の重みには非対応
- Pythonでの実装は簡単で、実用シーンも多い
- AIやゲーム・地図・物流最適化など幅広く応用可能！
