Dijkstra 算法
最后更新
Dijkstra 算法在边权非负的图中，求出从源节点到其他每个节点的最短路径。它为每个节点维护一个暂定距离，反复从未确定的节点中选出暂定距离最小的那个并将其确定下来，然后松弛它的边：只要经过当前节点能找到更短的路线，就更新邻居的距离。点击上方的“播放”，观察每确定一个节点，距离如何随之下降。
关键思想是贪心：一旦选出最近的未确定节点，它的距离就是最终结果，因为通往它的其他路线都必须经过一个本来就更远的节点。使用二叉堆实现的优先队列时，Dijkstra 的运行时间是 O((V + E) log V)。它要求权重非负，如果边可能为负，请使用 Bellman-Ford。
时间和空间复杂度
| 实现方式 | 复杂度 | 说明 |
|---|---|---|
| 二叉堆 | 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，没有可松弛的边了，结束。 |
什么时候使用 Dijkstra 算法
| 适合使用的情况 | 不适合使用的情况 |
|---|---|
| 所有边的权重都非负 | 有边可能为负，应使用 Bellman-Ford |
| 需要从一个源点到所有节点的最短路径 | 需要所有点对之间的最短路径，Floyd-Warshall 更简单 |
| 图带有权重，并且需要精确的距离 | 图没有权重，普通 BFS 更快也更简单 |
| 手头有好用的堆或优先队列 | 想借助启发式快速到达单个目标，应使用 A* |
Dijkstra's Algorithm 代码
简洁、可运行的 Dijkstra's Algorithm 实现，提供 Python, JavaScript, Java, C++, C 版本。选择一种语言，复制代码，或在 Coddy 在线编辑器中直接打开。
Dijkstra's Algorithm 的 Python 代码
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}")Dijkstra's Algorithm 的 JavaScript 代码
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"));Dijkstra's Algorithm 的 Java 代码
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}Dijkstra's Algorithm 的 C++ 代码
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}Dijkstra's Algorithm 的 C 代码
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}Dijkstra 算法常见问题
Dijkstra 算法的时间复杂度是多少？
使用二叉堆实现的优先队列时，运行时间是
O((V + E) log V)。每一步都扫描数组找最小值的简单版本是 O(V²)，在稠密图上反而可能更快。两者都占用 O(V) 的空间。为什么 Dijkstra 不能处理负权边？
Dijkstra 假设一旦确定了最近的未确定节点，这个距离就是最终结果。负权边可能在之后为一个已确定的节点产生更短的路径，从而打破这个假设。对于有负权边的图，请使用 Bellman-Ford 算法。
Dijkstra 和 BFS 有什么区别？
BFS 用普通队列，按边数求最短路径（相当于每条边的权重都是 1）。Dijkstra 把这个思路推广到带权图：借助优先队列，始终扩展总距离最小的节点。在无权图上，两者得到的路径相同。
Dijkstra 和 A* 搜索有什么区别？
A* 就是 Dijkstra 加上一个估算到目标剩余距离的启发函数，所以它会把搜索引向目标，而不是向所有方向均匀扩展。当启发函数为零时，A* 就退化成 Dijkstra。如果只有一个终点，并且有好的可采纳启发函数，就用 A*；如果需要到每个节点的距离，就用 Dijkstra。
什么时候该用 Dijkstra 而不是 Bellman-Ford？
只要所有边的权重都非负，就用 Dijkstra，它的
O((V + E) log V) 比 Bellman-Ford 的 O(V·E) 更快。只有当边可能为负，或者需要检测负权回路时，才选择 Bellman-Ford。在非负权图上，Dijkstra 几乎总是更好的选择。节点确定之后，Dijkstra 还会再访问它吗？
不会。节点一旦确定，它的距离就是最终结果，不会再被松弛。堆实现中一个常见的坑是：节点的距离变小后，优先队列里还留着过时的条目。如果弹出的节点已经确定（弹出的距离大于记录的距离），就必须跳过它。忘了这个检查，结果仍然正确，但会做很多无用功。
相关资源
更多可视化
