如何在无负环且含k条负权边的有向图中求解起点到所有顶点的最短路径?
含少量负权边、无负权环的有向图单源最短路高效实现方案
直接跑Bellman-Ford需要完成n-1轮全边松弛,时间复杂度为O(nm);SPFA虽然通过队列减少了无效松弛,但在负权边集中分布的图上很容易出现节点被反复入队的退化,最坏依然会落到O(nm)的复杂度。在题设“图中共包含k条负权边、不存在负权环”的结构约束下,完全可以通过权值重构把问题转换为纯正权图最短路求解,接入效率稳定的Dijkstra框架,整体性能远好于直接在原带负权图上跑松弛类算法,可根据k的规模选择对应实现:
方案一:通用Johnson重赋权改造(不依赖k的大小)
这是适用范围最广的改造方案,不受负权边数量多少的限制,实现逻辑清晰稳定:
- 新增一个虚拟源点,从该点向图内所有其他顶点连一条权值为0的有向边。
- 在包含虚拟源点的图上计算一次从虚拟源点出发的全图最短路,得到每个顶点的势函数值
h[v]。这一步的计算因为仅涉及k条负权边,就算用SPFA实现也不会出现严重的退化问题,整体耗时极低。 - 对原有的每一条有向边
u->v,将原权值w(u,v)重新计算为新权值:w'(u,v) = w(u,v) + h[u] - h[v]。根据最短路三角不等式可证明,计算得到的所有新边权均为非负值。 - 删除虚拟源点,在新的全非负权图上从你指定的实际起始点
s运行标准Dijkstra算法,得到新图上的最短路值d'[v]。 - 最后将结果还原为原权值下的真实最短距离:
d[v] = d'[v] + h[v] - h[s]。
该方案的整体时间复杂度为O(m + n log n),没有SPFA的最坏退化风险,运行效率的稳定性远高于直接在原带负权的图上跑松弛类算法。
方案二:k值极小时的定向优化(k远小于总边数m)
当负权边的总数量k非常少(比如k为个位数、远低于总边数m)的时候,可以跳过全图的势函数计算,进一步压缩运行时间:
- 先从原有的图里把所有k条负权边摘出去,剩下的全是正权边组成的子图。
- 从实际起始点
s出发,在这个正权子图上跑一次标准Dijkstra,得到所有顶点的初步最短距离d0[v]。 - 遍历所有摘掉的负权边,对每条边
u->v(权值为w)做松弛判断:如果d0[v] > d0[u] + w,说明这条负权边可以带来更短的路径,就把v作为额外源点,在正权子图上跑一次多源最短路,更新所有关联顶点的距离值。 - 重复遍历判断直到没有可以通过负权边更新的更短路径,因为图不存在负权环,整个松弛过程最多循环k次就会完全收敛。
该方案的整体时间复杂度为O(k*(m + n log n)),在k值很小的场景下,运行速度会比Johnson方法还要快。
注意:所有改造方法的有效性都建立在题设的“无负权环”前提上,如果后续图结构变化出现负权环,需要额外增加环检测逻辑,不能直接套用上述流程。
内容的提问来源于stack exchange,提问作者MissSirius
相关产品推荐
相关产品推荐

