You need to enable JavaScript to run this app. 如何在无负环且含k条负权边的有向图中求解起点到所有顶点的最短路径?
优惠活动
大模型
产品
解决方案
定价
更多

如何在无负环且含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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.13 12:36:10