先记住这个答案
朴素实现每轮扫描所有未标记顶点找最小值，共 V 轮，每轮 O(V)，加松弛 O(E)，总计 O(V²+E)。二叉堆实现则用优先队列维护未确定顶点，每次弹出最小值 O(logV)，每条边可能被松弛一次并推入堆，总计 O((V+E)logV)。因此稠密图（E≈V²）用朴素数组更快，稀疏图用堆更优。
- 朴素数组实现 O(V²)，稠密图更优
- 二叉堆实现 O((E+V)logV)，稀疏图更优
- 当 V 大且 E 接近 V² 时选朴素数组
复杂度从何而来
朴素实现用数组 d[] 存储当前距离，每轮线性扫描找出未标记顶点中 d 最小者，故每轮开销 O(V)，共 V 轮，总 O(V²)。每条边松弛一次 O(1)，总 O(V²+E)。该实现不利用距离分布，即使 E 很小也要做满 V² 扫描。
二叉堆实现将候选顶点按距离存入最小堆，堆操作 O(logV)。若不使用 decrease-key，每个顶点可能因距离更新而多次入堆，堆中元素最多 O(E)。每次弹出和压入各 O(logV)。松弛总数 E，总时间复杂度 O((V+E)logV)。注意实际实现常使用 decrease-key 或直接插入，直接插入后堆元素可达 E。
// 朴素数组实现 O(V^2)
function dijkstraArray(adj, V, s) {
let dist = Array(V).fill(Infinity);
let used = Array(V).fill(false);
dist[s] = 0;
for (let i = 0; i < V; i++) {
let v = -1;
for (let j = 0; j < V; j++) {
if (!used[j] && (v === -1 || dist[j] < dist[v])) v = j;
}
if (dist[v] === Infinity) break;
used[v] = true;
for (let [to, w] of adj[v]) {
if (dist[v] + w < dist[to]) dist[to] = dist[v] + w;
}
}
return dist;
}
// 二叉堆实现 O((V+E)logV)
function dijkstraHeap(adj, V, s) {
class MinHeap {
constructor() { this.heap = []; }
push(x) { this.heap.push(x); this._up(this.heap.length-1); }
pop() { let top = this.heap[0]; let last = this.heap.pop(); if (this.heap.length > 0) { this.heap[0] = last; this._down(0); } return top; }
_up(i) { while (i > 0) { let p = (i-1)>>1; if (this.heap[p][1] <= this.heap[i][1]) break; [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]]; i = p; } }
_down(i) { let n = this.heap.length; while (true) { let l = i*2+1, r = i*2+2, m = i; if (l < n && this.heap[l][1] < this.heap[m][1]) m = l; if (r < n && this.heap[r][1] < this.heap[m][1]) m = r; if (m === i) break; [this.heap[i], this.heap[m]] = [this.heap[m], this.heap[i]]; i = m; } }
}
let dist = Array(V).fill(Infinity);
let heap = new MinHeap();
dist[s] = 0;
heap.push([s, 0]);
while (heap.heap.length) {
let [v, d] = heap.pop();
if (d > dist[v]) continue;
for (let [to, w] of adj[v]) {
if (dist[v] + w < dist[to]) {
dist[to] = dist[v] + w;
heap.push([to, dist[to]]);
}
}
}
return dist;
}
// 测试：无向图顶点 0-2
let adj = [
[[1, 1], [2, 4]],
[[0, 1], [2, 1]],
[[0, 4], [1, 1]]
];
console.log('朴素:', JSON.stringify(dijkstraArray(adj, 3, 0)));
console.log('堆:', JSON.stringify(dijkstraHeap(adj, 3, 0)));
// 稀疏图：顶点 5 边 5
let adj2 = [
[[1, 2]],
[[2, 3]],
[[3, 1]],
[[4, 5]],
[]
];
console.log('稀疏朴素:', JSON.stringify(dijkstraArray(adj2, 5, 0)));
console.log('稀疏堆:', JSON.stringify(dijkstraHeap(adj2, 5, 0)));查看输出与解释
朴素: [0,1,2]
堆: [0,1,2]
稀疏朴素: [0,2,5,6,11]
稀疏堆: [0,2,5,6,11]JavaScript 实现展示两种精度的 Dijkstra。数组实现每次 O(V) 搜索，堆实现用最小堆保证每次取出当前最小距离。测试了完全图和稀疏图，结果一致。
社交网络好友推荐的最短路建模
假设有 V=10^5 个用户，每个用户平均关注 20 人，总边 E≈2×10^6。要计算某个用户到其他所有人的最短路径长度，这是稀疏图。此时朴素数组每轮 O(V) 扫描需 10^10 次操作，完全不可行；堆实现 O((V+E)logV)≈(2.1×10^6)×17≈3.6×10^7 操作，毫秒级完成。
如果换成稠密图，例如航线网络中 V=10^3 城市两两之间有直飞，E≈5×10^5，则朴素 O(V²)=10^6 比堆 O((V+E)logV)≈(5×10^5)×10≈5×10^6 更优。实际工程中需要根据边数选择实现。
复杂度陷阱与前提
二叉堆实现的 O((V+E)logV) 是在没有负权边的前提下的。若允许边权更新频繁导致堆中冗余元素，堆大小可能达到 O(E)，但 E 本身小于 V²，理论复杂度不变。不过当 E 接近 V² 时，log V 系数使得常数增大，可能不如 O(V²)。
当图特别稀疏（E=O(V)）时，堆实现退化为 O(V log V)，而朴素数组仍是 O(V²)。但若 V 很小（如 V≤1000），O(V²) 和 O(V log V) 差距不大，此时实现简单即可。注意堆实现每次松弛推送新距离，实际堆操作次数为 E 次，内存占用 O(E)。
容易答错的地方
- 认为堆优化总是更快
- 实际上当图接近完全图时，O(V²) 的朴素实现比 O((V+E)logV) 更快，因为后者堆操作 logV 因子在 E≈V² 时膨胀为 V² logV，远大于 V²。要依据边密度选择。
- 混淆二叉堆与斐波那契堆复杂度
- 有些资料称 Dijkstra 最优为 O(E+V logV)，那是斐波那契堆的理论复杂度。二叉堆版本是 O((V+E)logV)，两者不同。本文只讨论二叉堆和朴素数组。
面试官还会怎么问？
用 `priority_queue` 时顶点可能重复入队，会影响复杂度吗？
不会，重复入队总数不超过 E 次，堆大小 O(E)，每次操作 O(logE)=O(logV)，总复杂度仍为 O((V+E)logV)，但常数较大。可加跳过过期元素的时间检查。
图非常稀疏且 V 巨大时，还能无限优化吗？
可以改用斐波那契堆达到 O(E+V logV)，但实现复杂。若度数接近 1 且 V 达 10^7，O(V logV) 也可能吃紧。若边权仅为 0 或 1，可使用双端队列 BFS（0-1 BFS）将复杂度降至 O(V+E)；若边权为非负整数，也可用 Dial 桶优化；但一般非负实权时没有特别简单的优化。
为什么堆实现中松弛操作需要 O(logV)，而朴素数组是 O(1)？
堆需要维持候选集有序以快速弹最小值，插入或更新后要上浮/下沉。朴素数组更新距离直接改 d[to]，但查找最小值时得线性扫描。两种操作权衡不同。
参考资料
示例用于理解所注明的运行环境与边界；延伸学习可结合原文中的更多案例。