1. 概述
Dijkstra 算法是图中最经典的最短路径查找算法之一，其核心在于使用优先队列（Priority Queue）来高效地选择当前距离源点最近的节点进行扩展。这与广度优先搜索（BFS）有显著区别，也是 Dijkstra 算法性能优化的关键点之一。
在本文中，我们将探讨 Dijkstra 算法的三种实现方式：
- 基础实现（Naive）：使用普通的优先队列，但效率较低；
- 使用 Eager Removal 的优化实现；
- 使用 Decrease-Key 的优化实现，适用于某些高级堆结构（如 Fibonacci Heap）。
我们会分析每种实现的时间复杂度，并指出在不同场景下哪种方式更适合。
2. Dijkstra 算法回顾
Dijkstra 算法的核心思想是：
- 从源点出发，逐步更新图中每个节点的最短路径；
- 使用优先队列选择当前距离最小的节点进行扩展；
- 每次扩展后更新其邻居节点的路径信息。
下面是通用的 Dijkstra 算法伪代码（适用于求源点到所有节点的最短路径）：
algorithm DijkstrasAlgorithm(G, s):
// INPUT
// G = 图 G(V, E)
// s = 源节点
// OUTPUT
// d = 每个节点的最短距离
// p = 路径前驱节点
for v in V[G]:
d[v] <- +infinity
p[v] <- undefined
d[s] <- 0
S <- 空集合 // 已访问节点集合
Q <- V[G]
while Q not empty:
u <- Q 中 d[u] 最小的节点
if u not in S:
S <- S + {u}
for 每条 u 的出边 (u, v):
if d[u] + w(u, v) < d[v]:
d[v] <- d[u] + w(u, v)
p[v] <- u
return (d, p)
在实际应用中，我们往往只需要求源点到某个终点的最短路径。此时可以对算法进行优化，提前退出循环：
algorithm Dijkstra(G, s, f):
// INPUT
// G = 图 G(V, E)
// s = 源节点
// f = 目标节点
// OUTPUT
// d[f] = 到目标节点的最短路径长度
// sp = 路径节点集合
初始化 d 和 p 数组...
while Q not empty:
u <- Q 中 d[u] 最小的节点
if u == f:
break
if u not in S:
S <- S + {u}
for 每条 u 的出边 (u, v):
if d[u] + w(u, v) < d[v]:
更新 d[v] 和 p[v]
return 最短路径和长度
3. 基础实现（Naive）
这是一种常见但效率较低的实现方式。它的核心问题是：
✅ 每次发现更短路径时，不是更新已存在的节点权重，而是直接插入新记录，导致优先队列中出现大量重复节点。
这会带来以下问题：
❌ 优先队列大小可能达到边数级别（O(E)）
❌ 插入和取出操作的时间复杂度为 O(log E)
❌ 总体时间复杂度为 O(E log E)
下面是该实现的伪代码：
algorithm DijkstrasNaive(G, s, f):
初始化 d 和 p...
Q <- {(s, 0)}
while Q not empty:
(u, w) <- Q 中最小权重的节点
if u == f:
break
if u not in S:
S <- S + {u}
for 每条 u 的出边 (u, v):
if d[u] + w(u, v) < d[v]:
d[v] <- d[u] + w(u, v)
Q <- Q + {(v, d[v])}
p[v] <- u
return 最短路径和长度
⚠️ 注意：这种实现虽然简单，但在稠密图或大规模图中效率非常低，容易成为性能瓶颈。
4. 提升性能的两种方式
为了减少队列中重复节点的数量，我们可以采用以下两种策略：
4.1. Eager Removal（主动移除旧节点）
每次插入新节点之前，先检查队列中是否已有该节点，如果存在则先将其移除，再插入新的权重值。
这样可以保证队列中每个节点最多出现一次，从而将队列大小控制在 O(V) 内。
algorithm DijkstraEagerRemoval(G, s, f):
Q <- 空优先队列
Q.enqueue(s, 0)
while Q not empty:
(u, wu) <- Q 中最小权重的节点
if u == f:
break
if u not in S:
S <- S + {u}
for 每条 u 的出边 (u, v):
(v, wv) <- Q.peek(v)
if wu + w(u, v) < wv:
if v in Q:
Q.dequeue(v)
Q.enqueue(v, wu + w(u, v))
p[v] <- u
✅ 优点：
- 队列大小为 O(V)
- 插入和取出操作为 O(log V)
❌ 缺点：
- 需要一个支持快速查找和删除的优先队列结构（如 Indexed Heap）
4.2. Decrease-Key 实现
另一种更优雅的方式是使用 支持 Decrease-Key 操作的优先队列（如 Fibonacci Heap）。
当发现更短路径时，直接更新队列中已有节点的权重，而不是插入新节点。
algorithm DijkstrasDecreaseKey(G, s, f):
Q <- 空优先队列
Q.enqueue(s, 0)
while Q not empty:
(u, wu) <- Q 中最小权重的节点
if u == f:
break
if u not in S:
S <- S + {u}
for 每条 u 的出边 (u, v):
(v, wv) <- Q.peek(v)
if wu + w(u, v) < wv:
Q.decreaseKey(v, wu + w(u, v))
p[v] <- u
✅ 优点：
- 队列大小仍为 O(V)
- 插入和取出为 O(log V)
- Decrease-Key 操作为 O(1)（如使用 Fibonacci Heap）
❌ 缺点：
- 实现复杂度高
- 部分语言标准库不支持
4.3. 改进型 Decrease-Key 实现
使用 Fibonacci Heap 等高级数据结构，可以将 Decrease-Key 的时间复杂度降至 O(1) 摊销时间，从而将 Dijkstra 算法的总体时间复杂度优化为：
✅ O(E + V log V)
这在图中边数远大于节点数时（如稠密图）有显著优势。
⚠️ 但需要注意：
- 摊销时间意味着单次操作可能较慢
- 实现复杂，调试难度大
- 在 Java、Python 等语言中不常见，需要手动实现
5. 时间复杂度对比分析
下表总结了几种优先队列实现方式下的 Dijkstra 算法时间复杂度：
| 队列类型 | 入队 Enqueue | 出队 Dequeue | Decrease-Key | 有 Decrease-Key 时 | 无 Decrease-Key 时 |
|---|---|---|---|---|---|
| 二叉堆 Binary Heap | O(log V) | O(log V) | O(log V) | O(E log V) | O(E log V) |
| 二项堆 Binomial Heap | O(log V) | O(log V) | O(log V) | O(E log V) | O(E log V) |
| 斐波那契堆 Fibonacci Heap（摊销） | O(1) | O(log V) | O(1) | O(E + V log V) | O(E log V) |
✅ 结论：
- 使用 Binary Heap 时，Decrease-Key 并未带来显著性能提升；
- 使用 Fibonacci Heap 时，整体性能显著提升；
- 但在实际开发中，更推荐使用 Eager Removal + Indexed Heap 的方式模拟 Decrease-Key。
6. 总结
Dijkstra 算法的性能瓶颈在于优先队列的实现方式。通过使用支持 Decrease-Key 的数据结构（如 Fibonacci Heap），可以将算法的时间复杂度优化至 O(E + V log V)，尤其适用于稠密图。
但在大多数实际项目中：
✅ 推荐使用以下策略：
- 使用支持快速查找的优先队列（如 Indexed Heap）
- 通过 Eager Removal 模拟 Decrease-Key 操作
- 避免队列中出现大量重复节点
⚠️ 注意：不要盲目使用 Naive 实现，尤其在处理大规模图时容易出现性能问题。