ダイクストラ法
最終更新
ダイクストラ法は、非負の辺の重みを持つグラフにおいて、始点ノードから他のすべてのノードへの最短経路を求めます。各ノードに暫定距離を保持し、暫定距離が最小の未確定ノードを繰り返し確定させ、その辺を緩和します。現在のノードを経由するより短い経路が見つかるたびに隣接ノードの距離を更新します。上部の再生ボタンを押すと、各ノードが確定するにつれて距離が下がる様子を確認できます。
重要な洞察は貪欲であることです。最も近い未確定ノードが選ばれると、その距離は確定します。なぜなら、そのノードへの他のすべての経路は、すでにより遠いノードを通らなければならないからです。二分ヒープの優先度付きキューを用いると、ダイクストラ法は O((V + E) log V) 時間で実行されます。非負の重みが必要です。辺が負になり得る場合はベルマン・フォード法を使ってください。
時間計算量と空間計算量
| 実装 | 計算量 | 備考 |
|---|---|---|
| 二分ヒープ | O((V + E) log V) | 一般的で実用的な選択 |
| 配列走査 | O(V²) | より単純。密なグラフに適する |
| 空間 | O(V) | 距離 + 優先度付きキュー |
| 必要条件 | 非負の重み | 負の辺は貪欲な選択を壊す |
ステップごとの流れ
| ステップ | 何が起こるか |
|---|---|
| 1 | 始点の距離を 0 に、それ以外をすべて無限大に設定する。 |
| 2 | 暫定距離が最小の未確定ノードを選ぶ。 |
| 3 | それを確定済みとする。最短距離がここで確定する。 |
| 4 | 各隣接ノードについて、現在経由の距離 + 辺の重みを計算する。 |
| 5 | それが隣接ノードの現在の距離より小さければ緩和する。 |
| 6 | 到達可能なすべてのノードが確定するまで繰り返す。 |
具体例で追う
辺 A-B=4、A-C=1、C-B=2、C-D=5、B-D=1 を持つグラフで始点 A からの最短経路:
| ステップ | 確定 | 距離 | 動作 |
|---|---|---|---|
| 0 | - | A=0, B=∞, C=∞, D=∞ | 初期化: 始点 A=0、それ以外はすべて無限大。 |
| 1 | A (0) | B=4, C=1, D=∞ | A からの辺を緩和: B=4、C=1 に設定。 |
| 2 | C (1) | B=3, D=6 | C 経由: B=1+2=3 が 4 を更新。D=1+5=6。 |
| 3 | B (3) | D=4 | B 経由: D=3+1=4 が 6 を更新。 |
| 4 | D (4) | A=0, C=1, B=3, D=4 | D を確定。緩和すべきものはもうない。完了。 |
ダイクストラ法を使うべき場面
| 使うべき場面 | 避けるべき場面 |
|---|---|
| すべての辺の重みが非負のとき | いずれかの辺が負になり得るとき: ベルマン・フォード法を使う |
| 1 つの始点から全ノードへの最短経路が必要なとき | 全ペア間の最短経路が必要なとき: ワーシャル・フロイド法の方が単純 |
| グラフが重み付きで正確な距離が欲しいとき | グラフが重みなしのとき: 単純な BFS の方が速く単純 |
| 優れたヒープや優先度付きキューが使えるとき | ヒューリスティックで単一の目的地に速く到達したいとき: A* を使う |
Dijkstra's Algorithmのコード
Python, JavaScript, Java, C++, Cによるクリーンで実行可能なDijkstra's Algorithmの実装です。言語を選んでコードをコピーするか、Coddyプレイグラウンドに読み込んだ状態で開けます。
PythonでのDijkstra's Algorithmのコード
Python
1import heapq2
3
4def dijkstra(graph, start):5 dist = {node: float("inf") for node in graph}6 dist[start] = 07 pq = [(0, start)]8 while pq:9 d, node = heapq.heappop(pq)10 if d > dist[node]:11 continue # stale entry, a shorter path was already found12 for neighbor, weight in graph[node]:13 new_dist = d + weight14 if new_dist < dist[neighbor]:15 dist[neighbor] = new_dist16 heapq.heappush(pq, (new_dist, neighbor))17 return dist18
19
20graph = {21 "A": [("B", 4), ("C", 1)],22 "B": [("D", 1)],23 "C": [("B", 2), ("D", 5)],24 "D": [("E", 3)],25 "E": [],26}27
28for node, d in dijkstra(graph, "A").items():29 print(f"A -> {node}: {d}")JavaScriptでのDijkstra's Algorithmのコード
JavaScript
1const graph = {2 A: { B: 4, C: 2 },3 B: { C: 5, D: 10 },4 C: { E: 3 },5 D: { F: 11 },6 E: { D: 4 },7 F: {},8};9
10function dijkstra(source) {11 const dist = {};12 const visited = new Set();13 for (const node in graph) dist[node] = Infinity;14 dist[source] = 0;15 while (visited.size < Object.keys(graph).length) {16 // JS has no built-in heap: linear scan for the closest node (O(V^2))17 let u = null;18 for (const node in dist) {19 if (!visited.has(node) && (u === null || dist[node] < dist[u])) {20 u = node;21 }22 }23 if (dist[u] === Infinity) break;24 visited.add(u);25 for (const [v, w] of Object.entries(graph[u])) {26 if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;27 }28 }29 return dist;30}31
32console.log("Shortest distances from A:", dijkstra("A"));JavaでのDijkstra's Algorithmのコード
Java
1import java.util.ArrayList;2import java.util.Arrays;3import java.util.List;4import java.util.PriorityQueue;5
6public class Main {7 public static void main(String[] args) {8 int n = 6;9 List<List<int[]>> adj = new ArrayList<>();10 for (int i = 0; i < n; i++) adj.add(new ArrayList<>());11 int[][] edges = {12 {0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 5},13 {2, 3, 8}, {3, 4, 3}, {2, 5, 10}, {4, 5, 2}14 };15 for (int[] e : edges) {16 adj.get(e[0]).add(new int[]{e[1], e[2]});17 adj.get(e[1]).add(new int[]{e[0], e[2]});18 }19
20 int[] dist = new int[n];21 Arrays.fill(dist, Integer.MAX_VALUE);22 dist[0] = 0;23 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);24 pq.add(new int[]{0, 0}); // {node, distance}25 while (!pq.isEmpty()) {26 int[] cur = pq.poll();27 int node = cur[0], d = cur[1];28 if (d > dist[node]) continue; // stale queue entry29 for (int[] edge : adj.get(node)) {30 int next = edge[0], nd = d + edge[1];31 if (nd < dist[next]) {32 dist[next] = nd;33 pq.add(new int[]{next, nd});34 }35 }36 }37 System.out.println("Shortest distances from 0: " + Arrays.toString(dist));38 }39}C++でのDijkstra's Algorithmのコード
C++
1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6 const int INF = 1000000000;7 // Weighted directed graph: adj[u] = {(neighbor, weight), ...}8 std::vector<std::vector<std::pair<int, int>>> adj = {9 {{1, 4}, {2, 1}}, // 010 {{3, 1}}, // 111 {{1, 2}, {3, 5}}, // 212 {{4, 3}}, // 313 {}, // 414 };15 int n = static_cast<int>(adj.size());16 std::vector<int> dist(n, INF);17 dist[0] = 0;18 using State = std::pair<int, int>; // (distance, node)19 std::priority_queue<State, std::vector<State>, std::greater<State>> pq;20 pq.push({0, 0});21 while (!pq.empty()) {22 auto [d, u] = pq.top();23 pq.pop();24 if (d > dist[u]) continue; // stale queue entry25 for (auto [v, w] : adj[u]) {26 if (d + w < dist[v]) {27 dist[v] = d + w;28 pq.push({dist[v], v});29 }30 }31 }32 for (int v = 0; v < n; ++v) {33 std::cout << "Distance 0 -> " << v << ": " << dist[v] << "\n";34 }35 return 0;36}CでのDijkstra's Algorithmのコード
C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 55#define INF 10000000006
7int main(void) {8 // Weighted directed graph: w[u][v] = 0 means no edge9 int w[N][N] = {10 {0, 4, 1, 0, 0},11 {0, 0, 0, 1, 0},12 {0, 2, 0, 5, 0},13 {0, 0, 0, 0, 3},14 {0, 0, 0, 0, 0},15 };16 int dist[N];17 bool done[N] = {false};18 for (int v = 0; v < N; v++) dist[v] = INF;19 dist[0] = 0;20 // O(V^2) scan for the closest unfinished node (no heap needed here)21 for (int iter = 0; iter < N; iter++) {22 int u = -1;23 for (int v = 0; v < N; v++) {24 if (!done[v] && (u == -1 || dist[v] < dist[u])) u = v;25 }26 if (dist[u] == INF) break; // remaining nodes are unreachable27 done[u] = true;28 for (int v = 0; v < N; v++) {29 if (w[u][v] > 0 && dist[u] + w[u][v] < dist[v]) {30 dist[v] = dist[u] + w[u][v];31 }32 }33 }34 for (int v = 0; v < N; v++) {35 printf("Distance 0 -> %d: %d\n", v, dist[v]);36 }37 return 0;38}ダイクストラ法に関するよくある質問
ダイクストラ法の時間計算量はどのくらいですか？
二分ヒープの優先度付きキューを用いると
O((V + E) log V) で実行されます。各ステップで配列を走査して最小値を探す単純な版は O(V²) で、密なグラフではむしろこちらの方が速いことがあります。どちらも空間は O(V) です。なぜダイクストラ法は負の辺の重みで機能しないのですか？
ダイクストラ法は、最も近い未確定ノードを確定した時点でその距離が確定すると仮定します。負の辺は、あとから確定済みのノードへのより短い経路を作り出し、この仮定を壊す可能性があります。負の重みを持つグラフにはベルマン・フォード法を使ってください。
ダイクストラ法と BFS の違いは何ですか？
BFS は辺を数えて（各辺の重みは実質 1）、単純なキューを使って最短経路を求めます。ダイクストラ法はこれを重み付きグラフへ一般化し、優先度付きキューを使って常に合計距離が最小のノードを展開します。重みなしグラフでは両者は同じ経路を生成します。
ダイクストラ法と A* 探索の違いは何ですか？
A* は、目的地までの残り距離を見積もるヒューリスティックを加えたダイクストラ法で、全方向へ一様に広がる代わりに探索をその目標へ導きます。ヒューリスティックがゼロのとき、A* はちょうどダイクストラ法に帰着します。単一の目的地と良い許容的ヒューリスティックがあるときは A* を、全ノードへの距離が必要なときはダイクストラ法を使ってください。
ベルマン・フォード法ではなくダイクストラ法を使うべきなのはいつですか？
すべての辺の重みが非負であれば常にダイクストラ法を使ってください。ベルマン・フォード法の
O(V·E) に対して O((V + E) log V) と高速です。ベルマン・フォード法は、辺が負になり得るか、負閉路を検出する必要がある場合にのみ選びます。非負のグラフではダイクストラ法がほぼ常により良い選択です。ダイクストラ法は確定したノードを再訪することがありますか？
いいえ。ノードがいったん確定すると、その距離は確定し、二度と緩和されません。ヒープ実装でよくある落とし穴は、ノードの距離が改善した後に優先度付きキューへ古いエントリを残してしまうことです。取り出したノードがすでに確定済みなら（取り出した距離が記録された距離を上回るなら）スキップする必要があります。このチェックを忘れても答えは正しいままですが、無駄な処理が発生します。
関連リソース
その他の可視化
