Coding Interview Prep · 课时

Bellman-Ford 与负环

Q: 「Bellman-Ford 与负环」课时是免费的吗？

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

Q: 「Bellman-Ford 与负环」这节课中我会学到什么？

对所有边执行 n-1 轮松弛，通过最后一轮检测负环，并解释 Dijkstra 算法为什么无法处理负权边。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

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

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

Q: 「Bellman-Ford 与负环」课时需要多长时间？

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

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

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

对所有边执行 n-1 轮松弛，通过最后一轮检测负环，并解释 Dijkstra 算法为什么无法处理负权边。

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

贝尔曼-福特算法为何存在

贝尔曼-福特算法和戴克斯特拉算法一样，可以解决单源最短路径问题，但它能够处理负边权。它还可以检测负环——即总权重为负的环；经过这种环时，无法定义有限的最短路径。虽然贝尔曼-福特算法比戴克斯特拉算法慢，但只要图中可能包含负权边，它就是正确的选择。

松弛：核心操作

贝尔曼-福特算法建立在一个基本操作之上：松弛。松弛边 (u, v, w) 的含义是：如果 dist[u] + w < dist[v]，就更新 dist[v] = dist[u] + w。我们会反复松弛所有边。关键洞见是：在不存在负环的图中，任意最短路径最多包含 V-1 条边。因此，对所有边进行 V-1 轮松弛，就足以找到所有最短路径。

贝尔曼-福特算法实现

将图表示为边列表 [(u, v, weight)]。将 dist[source] = 0 初始化，并将其他所有距离设为 inf。执行 V-1 轮，每轮松弛所有边。如果在第 V 轮中仍然发生更新，则表示存在负环。

def bellman_ford(V, edges, source):
    dist = [float('inf')] * V
    dist[source] = 0
    
    # V-1 relaxation passes
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    
    # V-th pass: detect negative cycle
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None  # negative cycle exists
    
    return dist

edges = [(0,1,4),(0,2,5),(1,2,-3),(2,3,1)]
print(bellman_ford(4, edges, 0))  # [0, 4, 1, 2]

为何 V-1 轮就足够

在不存在负环的图中，最短路径最多访问每个节点一次，因此最多包含 V-1 条边。第 1 轮结束后，最短的 1 跳路径已经达到最优；第 2 轮结束后，最短的 2 跳路径已经达到最优。执行 V-1 轮后，所有最短路径（最多使用 V-1 跳）都已经找到。如果第 V 轮仍然更新某个距离，则表示图中存在一个从源点可达的负环。

负环检测

完成 V-1 轮后，再对所有边执行额外的一轮检查。如果某条边 (u, v, w) 满足 dist[u] + w < dist[v]，则表示存在负环，并且到达某些节点的最短路径为 -infinity。实际应用包括检测货币兑换中的套利机会（对数权重图中的负环），以及检测约束系统中的不一致。

def has_negative_cycle(V, edges, source):
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    # Nth pass
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return True  # negative cycle detected
    return False

# Negative cycle: 1->2->3->1 with weights -1,-1,1 (sum=-1)
edges_neg = [(0,1,1),(1,2,-1),(2,3,-1),(3,1,1)]
print(has_negative_cycle(4, edges_neg, 0))  # True

戴克斯特拉算法与贝尔曼-福特算法的比较

戴克斯特拉算法：O((V+E) log V)，要求边权为非负，采用贪心方法。贝尔曼-福特算法：O(V × E)，可以处理负权，能够检测负环。对于大多数边权为非负的面试题，通常优先选择戴克斯特拉算法。当出现负权（例如“查找包含负成本边的最短路径”或“检测套利”）时，应选择贝尔曼-福特算法。对于稠密图，贝尔曼-福特算法 O(V³) 的最坏情况复杂度与弗洛伊德-沃舍尔算法相当。

应用：使用贝尔曼-福特算法查找最低票价航班

最多 K 次中转的最低票价航班（LeetCode 787）可以使用修改后的贝尔曼-福特算法解决：恰好执行 k+1 轮松弛（因为 k 个中转站意味着 k+1 条边）。请使用上一轮距离的副本，以确保单轮中不会使用超过限制的跳数——否则一轮操作就可能连续经过多条边。

def findCheapestPrice_bf(n, flights, src, dst, k):
    dist = [float('inf')] * n
    dist[src] = 0
    
    for _ in range(k + 1):  # k stops = k+1 edges
        temp = dist[:]  # copy to avoid using updated dist in same pass
        for u, v, w in flights:
            if dist[u] != float('inf') and dist[u] + w < temp[v]:
                temp[v] = dist[u] + w
        dist = temp
    
    return dist[dst] if dist[dst] != float('inf') else -1

print(findCheapestPrice_bf(4,[[0,1,100],[1,2,100],[0,2,500]],0,2,1))  # 200

SPFA：基于队列的优化

最短路径更快算法（SPFA）是贝尔曼-福特算法的一种优化版本。它使用队列，只重新松弛那些距离刚刚更新的节点所关联的边。平均情况下的复杂度为 O(E)，但最坏情况仍然是 O(V × E)。面试中很少要求实现 SPFA，但当贝尔曼-福特算法在稀疏图上运行过慢时，可以将其作为一种优化方案提及。Python 没有内置的 SPFA，但使用 collections.deque 可以很容易地实现。

货币套利检测

这是贝尔曼-福特算法的经典应用：给定货币兑换汇率，检测是否存在套利可能（即兑换一圈货币后，所得金额比起始金额更多）。可以对汇率取负对数进行转换。套利等价于总 log 权重为负的环，也就是贝尔曼-福特算法可以检测到的负环。这种方法将现实中的金融问题转换成了标准算法问题。

import math

def has_arbitrage(rates):
    n = len(rates)
    # Transform: -log(rate) converts product to sum
    log_rates = [[-math.log(rates[i][j]) for j in range(n)] for i in range(n)]
    edges = [(i,j,log_rates[i][j]) for i in range(n) for j in range(n) if i != j]
    
    dist = [float('inf')] * n
    dist[0] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return True  # arbitrage!
    return False

提前终止优化

如果完整检查所有边的一轮操作中没有任何距离被更新，那么后续各轮也不会再有更新，可以提前终止。这项优化会在图经过少数几轮后就达到最优时，将最佳情况下的复杂度降至 O(E)。请在每轮开始时添加标志 updated = False；如果该标志在本轮结束后仍为 False，请立即退出。

def bellman_ford_optimised(V, edges, source):
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break  # no more improvements possible
    return dist

邻接表图上的贝尔曼-福特算法

当图以邻接表而不是边列表的形式给出时，请先将其转换为边列表，或者遍历邻接表中的所有条目并将其视为边。对于 V=1000、E=5000 的情况，V-1=999 轮操作，每轮扫描 5000 条边，共执行 4,995,000 次操作，完全处于时间限制之内。对于非常稠密的图（E ≈ V²），O(V³) 的最坏情况与弗洛伊德-沃舍尔算法相同，因此应根据具体场景进行选择。

from collections import defaultdict

def bellman_ford_adj(V, adj, source):
    # Convert adjacency list to edge list
    edges = [(u, v, w) for u in range(V) for v, w in adj[u]]
    dist = [float('inf')] * V
    dist[source] = 0
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist

快速检查

请测试您对本课中“数据结构与算法——编码面试准备”相关概念的理解。

课程回顾

本课学习了以下内容：贝尔曼-福特算法通过将所有边松弛 V-1 次来处理负权边；第 V 轮松弛中仍然发现改进，表示存在负环；该算法的复杂度为 O(V × E)，而戴克斯特拉算法的复杂度为 O((V+E) log V)。接下来将学习弗洛伊德-沃舍尔算法，用一次 O(V³) 的计算求解所有节点对之间的最短路径。

常见问题解答