0Pricing
Coding Interview Prep · 课时

Bellman-Ford 与负权边

处理负权并检测循环

Bellman-Ford 与负权边 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。

Dijkstra 失效的情况

Dijkstra 认为弹出的距离已经确定，但负权边之后可能让某条路径的代价更低。因此它会失效。

认识 Bellman-Ford

Bellman-Ford可以处理负权边。它比 Dijkstra 慢，但在无法信任贪心逻辑的情况下更加稳健。

核心操作

它会反复松弛每条边：如果 dist[u] 加上边权小于 dist[v]，就将 dist[v] 更新为这个更小的值。

if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w

需要多少轮

最短路径最多使用 V-1 条边，因此对每条边进行V-1 轮松弛，就足以确定所有距离。

for _ in range(n - 1):
    relax_all_edges()

初始化距离

将除源点为零以外的所有距离设为无穷大，这与使用 Dijkstra 时完全相同。

dist = [float('inf')] * n
dist[src] = 0

一轮完整遍历

每一轮都会完整遍历一次边列表并松弛每条边。每轮会将改进结果向外传播一跳。

for u, v, w in edges:
    if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w

为什么 V-1 轮就够了

经过 k 轮后，使用 k 条边的所有最短路径都会正确。经过V-1 轮后，每条简单最短路径都已完成。

额外的一轮

再运行一轮。如果某个距离仍然下降，说明代价还在不断降低，这表明存在负环。

检测负环

负环意味着不存在有限的最短路径，因为您可以无限循环来让代价无限降低。

for u, v, w in edges:
    if dist[u] + w < dist[v]:
        return 'negative cycle'

运行时间

您需要在 V 轮中松弛 E 条边，因此 Bellman-Ford 的复杂度为O(V * E)，适合规模较小或中等的图。

Dijkstra 还是 Bellman-Ford

权重非负且追求速度时，请选择Dijkstra。出现负权边或必须检测异常环时，请选择 Bellman-Ford。

快速检查

经过 V-1 轮后，在额外一轮中某个距离仍然下降。这意味着什么？

回顾：Bellman-Ford

松弛所有边V-1 轮，再多做一轮来检测负环。它的复杂度是 O(V*E)，但能处理 Dijkstra 无法处理的情况。✅

常见问题解答

「Bellman-Ford 与负权边」课时是免费的吗？

是的 — 「Bellman-Ford 与负权边」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。

「Bellman-Ford 与负权边」这节课中我会学到什么？

处理负权并检测循环 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Coding Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。

「Bellman-Ford 与负权边」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Coding Interview Prep 课中编写并运行代码吗？

能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

  1. 使用堆实现 Dijkstra
  2. 使用双端队列实现 0-1 BFS
  3. Bellman-Ford 与负权边
  4. Floyd-Warshall 全点对算法
← 返回 Coding Interview Prep