上一篇我们讨论了Bellman-Ford算法它能处理任意带权图中的单源最短路径即便存在负权边也能正确完成代价是 Θ(∣V∣⋅∣E∣)Θ(∣V∣⋅∣E∣) 的时间复杂度。这个代价在实际应用中相当可观——一个包含十万个顶点和几十万条边的图可能需要数十亿次松弛操作。然而如果所有边的权重都非负我们完全可以用一种更聪明的方式组织松弛顺序从而大幅提升效率。这就是Dijkstra算法的核心贡献。一、非负权值的意义与贪心直觉为何负权边会让问题变难直观上一条负权边可能让看起来绕远的路径反而更短因此我们无法在“看到”一个顶点时就断言已找到其最短距离——后续可能通过某条负权边再绕回来产生更短的通路。Bellman-Ford的保守策略——反复松弛所有边——正是为了应对这种“后发先至”的可能性。而当所有边权非负时一个简洁的单调性成立了如果从源点出发沿着任意路径向前走路径的总长度只会增加或持平绝不会减少。这意味着一旦我们找到了从源点到某个顶点的“当前最短”路径并且该顶点的距离在所有未处理顶点中是最小的那么这条路径就一定是全局最短路径——因为任何试图绕道其他未处理顶点来改进它的尝试都需要先走过一个至少同样长的前缀再加上一条非负的后续路径总长度不可能更短。这个直觉正是Dijkstra算法的灵魂。二、算法框架与优先队列的角色Dijkstra算法维护一个顶点集合 SS其中所有顶点的最短距离已确定。初始时 S∅S∅d[s]0d[s]0其余 d[v]∞d[v]∞。每一步从未进入 SS 的顶点中选出一个 dd 值最小的顶点 uu将其加入 SS然后对 uu 的所有出边 (u,v)(u,v) 执行松弛操作。这一“选取最小 dd 值顶点”的操作正是优先队列的用武之地。标准的算法流程如下初始化距离数组 dd 和前驱数组 ππ将所有顶点插入优先队列 QQ键值为 dd。当 QQ 非空时取出键值最小的顶点 uu即 Extract-MinExtract-Min对 uu 的每条出边 (u,v)(u,v)若 d[v]d[u]w(u,v)d[v]d[u]w(u,v)则更新 d[v]d[v] 并在 QQ 中调整 vv 的键值即 Decrease-KeyDecrease-Key。优先队列在此承担了两个核心操作Extract-MinExtract-Min取出最小距离顶点和 Decrease-KeyDecrease-Key更新某顶点的距离键值。整个算法过程中前者执行恰好 ∣V∣∣V∣ 次后者至多执行 ∣E∣∣E∣ 次每条边至多触发一次键值下降。优先队列的实现方式直接决定了这两个操作的代价进而决定了Dijkstra算法的整体效率。三、二叉堆实现经典而普适的选择二叉堆是最常用的优先队列实现。一个包含 nn 个元素的二叉堆上Extract-MinExtract-Min 操作为 O(logn)O(logn)取出堆顶后需要将末元素移至堆顶并执行一次向下调整Decrease-KeyDecrease-Key 操作同样为 O(logn)O(logn)沿堆向上逐层调整。代入Dijkstra算法∣V∣∣V∣ 次取最小操作贡献 O(∣V∣log∣V∣)O(∣V∣log∣V∣)至多 ∣E∣∣E∣ 次键值下降操作贡献 O(∣E∣log∣V∣)O(∣E∣log∣V∣)。总和为 O((∣V∣∣E∣)log∣V∣)O((∣V∣∣E∣)log∣V∣)在稀疏图中近似为 O(∣E∣log∣V∣)O(∣E∣log∣V∣)。这是工程实践中最常见的Dijkstra实现。二叉堆结构简单常数因子小STL如C的priority_queue和多数标准库均直接提供。需要注意的是标准库的优先队列通常不直接支持 Decrease-KeyDecrease-Key常见的绕过手段是直接将更新后的顶点重新插入堆中而非原地修改键值并在取出时跳过已处理的顶点。这会略微增加堆中元素数量但渐进复杂度不变。四、斐波那契堆理论上的更优选择斐波那契堆是一个更为精巧的优先队列结构。其核心思想是惰性延迟——插入和合并操作不立即整理堆结构而是将工作推迟到取出最小元素时集中完成。借助这种策略斐波那契堆实现了以下平摊界Extract-MinExtract-Min 为 O(logn)O(logn)而 Decrease-KeyDecrease-Key 的平摊代价仅为 O(1)O(1)。将斐波那契堆嵌入Dijkstra算法∣V∣∣V∣ 次 Extract-MinExtract-Min 总代价 O(∣V∣log∣V∣)O(∣V∣log∣V∣)∣E∣∣E∣ 次 Decrease-KeyDecrease-Key 总代价 O(∣E∣)O(∣E∣)。总复杂度降至 O(∣V∣log∣V∣∣E∣)O(∣V∣log∣V∣∣E∣)。当图足够稠密时∣E∣Ω(∣V∣log∣V∣)∣E∣Ω(∣V∣log∣V∣)∣E∣∣E∣ 项主导二叉堆和斐波那契堆的渐进复杂度相当。但当图为稀疏图∣E∣O(∣V∣)∣E∣O(∣V∣)时斐波那契堆版本给出 O(∣V∣log∣V∣)O(∣V∣log∣V∣) 而二叉堆版本为 O(∣V∣log∣V∣)O(∣V∣log∣V∣)——二者在此情形下恰好相同。斐波那契堆真正产生显著优势的场景是中等稠密程度的图且顶点规模极大Decrease-KeyDecrease-Key 调用次数远超 Extract-MinExtract-Min 的倍数。然而在实际工程中斐波那契堆的常数因子很大且实现复杂度高因此多见于理论分析而非实际部署。五、正确性证明Dijkstra算法的正确性证明核心在于论证每次被选入 SS 的顶点的 dd 值即为真正最短距离。常用的证明方法是对加入 SS 的顶点数量进行归纳。归纳假设在每次迭代开始时对任意 v∈Sv∈Sd[v]δ(s,v)d[v]δ(s,v) 成立对任意 v∉Sv∈/Sd[v]d[v] 是仅经过 SS 中顶点的路径中最短的距离。初始步S∅S∅ 时归纳假设平凡成立第一条无对象第二条对 d[s]0d[s]0 成立。归纳步设本步选取 u∉Su∈/S 且 d[u]d[u] 最小。需证 d[u]δ(s,u)d[u]δ(s,u)。反设存在一条比 d[u]d[u] 更短的 s⇝us⇝u 路径 pp。由于 s∈Ss∈S 而 u∉Su∈/S路径 pp 必在某个点第一次离开 SS——设此边为 (x,y)(x,y)其中 x∈Sx∈Sy∉Sy∈/S。路径 pp 的长度可分解为 ss 到 xx 的最短距离已知且正确因 x∈Sx∈S加上 w(x,y)w(x,y) 加上 yy 到 uu 的剩余距离。由于所有边权非负剩余距离 ≥0≥0故 pp 的总长 ≥d[x]w(x,y)≥d[x]w(x,y)。而 (x,y)(x,y) 已被松弛当 xx 加入 SS 时故 d[y]≤d[x]w(x,y)d[y]≤d[x]w(x,y)。综合得 d[y]≤length(p)d[u]d[y]≤length(p)d[u]与 uu 是 dd 值最小的未处理顶点矛盾。归纳步成立。此证明依赖于所有边权非负这一前提——正是“剩余距离 ≥0≥0”这一不等式使得通过其他顶点的绕道不可能产生更短路径。六、适用边界与后续展望Dijkstra算法在非负权图上是最优的单源最短路径算法下界方面存在算法在某些图上可略优于 O(mlogn)O(mlogn)但差距仅为对数因子。若图中存在负权边必须退回Bellman-Ford或先对图进行重赋权预处理如Johnson算法中对边权的势能调整。在地图导航、网络路由内部网关协议OSPF即基于Dijkstra算法、物流路径规划等几乎所有边权非负的现实场景中Dijkstra算法均是首选。下一篇我们将目光从单源最短路径拉向全局——全源最短路径问题。当需要计算图中所有顶点对之间的最短距离时Floyd-Warshall算法如何用简洁的三重循环给出答案以及Johnson算法如何结合Bellman-Ford与Dijkstra取长补短将是下一篇的核心议题。
