01先把问题说具体
有向边 0→1 权 4、0→2 权 5、1→2 权 −2。负边会让 Dijkstra 的确定步骤失效,怎样仍求最短路?
02一步步得到方法
先取消过早确定的承诺
Bellman–Ford 不把某个节点永久定案,而是反复检查每条边:若 dist[u]+w<dist[v],就改进 v。初始化源点为 0,其余正无穷;不可达点不能作为有效松弛起点。
按轮次理解:第 k 轮结束后,所有最多使用 k 条边的可达路径的最优值已经能被传播到。代码若原地更新,单轮可能传播更多边,但不会比这个保证更差。
为什么 V−1 轮足够
没有可达负环时,最短路可取不重复节点的简单路径,最多 V−1 条边。完成这些轮后再检查一轮,若仍可改进,就有从源点可达的负环。
负环可被反复绕行使路径代价无限下降,相关目标不存在有限最短值。本课返回 None 表示发现这种情况,不返回看似正常的有限数组。与源点不连通的负环不会影响这次单源结果。
把轮数解释为路径边数
同步版本第 k 轮在上一轮结果上扩展一条边,可解释为最多 k 条边的最短距离。原地松弛同一轮可能传播多条边,但 n−1 轮的充分性仍可由简单最短路径至多含 n−1 条边来理解。
只从已可达端点进行松弛,避免把无穷距离与负权相加误当有效路径。若第 n 轮仍能从可达部分改善,就存在影响相关路径的负环;若要求逐节点标记,还需从受影响点继续传播。
03把一个小例子完全算清楚
3 点有向图:0→1:4,0→2:5,1→2:−2。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 初始化 | [0,∞,∞] | 只知道源点 |
| 扫描第一轮 | [0,4,2] | 经 1 到 2 的代价为 4−2=2 |
| 下一轮 | 无变化 | 可以提前终止 |
| 额外检查 | 没有边可再改进 | 无可达负环 |
窄屏可左右滑动表格,阅读完整计算与理由。
允许负边不等于允许负环下仍有有限答案。
04为什么这个方法成立
- 每次更新都对应一条真实可达路径,所以不会凭空得到不存在的更短值。
- 逐轮松弛覆盖最多 k 条边路径,V−1 轮覆盖所有简单路径。
- 若此后还可改进,改进路径必重复节点,其中包含可降低代价的负环。
05把推导翻译成代码
Python · 可独立运行的教学实现
def bellman_ford(n, edges, source):
dist = [float("inf")]*n
dist[source] = 0
for _ in range(n-1):
changed = False
for u,v,w in edges:
if dist[u] != float("inf") and dist[u]+w < dist[v]:
dist[v] = dist[u]+w
changed = True
if not changed:
break
for u,v,w in edges:
if dist[u] != float("inf") and dist[u]+w < dist[v]:
return None
return dist逐个理解关键决定
dist[u] != float("inf")- 保证只传播源点可达路径,也使负环检测范围明确。
if not changed- 整轮没有改进后已达不动点,后续轮不会产生新信息。
06时间、空间与实现范围
最坏时间 O(VE),距离数组 O(V),输入边表 O(E)。
想恢复路径需记录 predecessor;发现负环后若要标出受影响目标,还需从环向外搜索。
07改变条件,检查哪里会出错
只要图里有任意负环就否定所有单源结果
不连通负环不影响当前源点;必须检查可达性。
检测到可达负环就声称每个节点距离都无穷小
只有可从该负环继续到达的节点受到影响;其他可达分支可能仍有有限最短距离。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
0→1:1、1→0:−2 有什么问题?
需要一点提示
绕一圈成本。
查看解析与答案
环成本 −1,可无限降低源点可达节点距离,返回 None。
无负边时为何仍可能选 Dijkstra?
需要一点提示
比较时间界。
查看解析与答案
Bellman–Ford 更一般但通常更慢;非负前提允许 Dijkstra 更高效地确定节点。
无向图里一条负边意味着什么?
需要一点提示
边可来回走。
查看解析与答案
按可重复走边的最短路定义,来回形成负成本闭游走,距离可无限下降。