文档教程示例工程【免费下载链接】CLRS:notebook:Solutions to Introduction to Algorithms项目地址https://gitcode.com/gh_mirrors/cl/CLRS点击查看免费下载本文以《算法导论》CLRS第 24 章 24.1 节为核心结合开源仓库 gh_mirrors/cl/CLRS 中对该节全部 6 道习题的解答系统讲解 Bellman-Ford 算法的松弛过程、路径松弛性质、负权回路检测与处理以及以m 1次提前终止为代表的一系列算法改进。读完本文你将能够手工推演 Bellman-Ford 的多轮松弛并追踪d与π值在存在负权回路时正确判断算法返回值并定位回路顶点并把 Bellman-Ford 的松弛思想推广到差分约束、矩阵乘法等更广阔的图算法场景。1. 本节背景为什么需要 Bellman-Ford单源最短路径问题Single-Source Shortest Paths要求给定带权有向图G (V, E)与源点s求出s到其余所有顶点的最短路径。与只能处理非负边权的 Dijkstra 算法其习题见 24.3.md不同Bellman-Ford 允许边权为负且能在算法结束时明确报告图中是否存在从源点可达的负权回路——这一能力在差分约束系统求解24.4.md、以及将单源问题表达为矩阵乘积25.1.md等场景中都是关键前提。Bellman-Ford 的核心只有两个动作初始化Initialize-Single-Sources.d 0其余顶点v.d ∞前驱v.π NIL松弛RELAX对每条边(u, v)若v.d u.d w(u, v)则更新v.d u.d w(u, v)并令v.π u。整个算法对全部|V| - 1条边执行|V| - 1轮松弛最后再做一轮检测若仍有边可松弛说明存在负权回路。时间复杂度O(VE)。以下逐题剖析 24.1.md 中的 6 道习题。2. 习题 24.1-1手工推演松弛过程与负权回路检测以顶点z为源点在图 24.4 的有向图上运行 Bellman-Ford。每一轮按图中同样的顺序松弛边并给出每轮之后的d与π值。随后把边(z, x)的权重改为 4再以s为源点重新运行算法。2.1 以 z 为源点的最终收敛结果经过|V| - 1轮完整松弛后各顶点的最短路径估计收敛为顶点stxyzd24690πzxysØz作为源点其d恒为 0、π为 NIL其余顶点的最短路径通过前驱链可完整回溯例如s ← zd 2、t ← x ← y ← s ← zd 4。2.2 以 s 为源点边 (z, x) 权重改为 4修改w(z, x) 4之后重新运行顶点stxyzd0047-2πØxzst注意t.d 0而t.π xz.d -2而z.π tx.π z。关键结论此时 Bellman-Ford 返回false因为图中出现了负权回路——由边(t, z)、(z, x)、(x, t)构成的环其总权重为负。一旦存在负权回路第|V|轮检测必然还能继续松弛算法据此判定无解。这道题直观展示了松弛的顺序无关性只要每轮遍历所有边以及负权回路如何让距离估计在每轮中持续变小而无法收敛。3. 习题 24.1-2推论 24.3 的证明思路证明推论 24.3Corollary 24.3若从源点s到顶点v不存在通路则初始化后v.d始终保持∞。本仓库给出的证明极为精炼如果没有通路则无法进行松弛。因为松弛操作RELAX(u, v)只有在边(u, v)存在时才会被触发且只有u.d为有限值时才能把有限值传播给v.d。若s到v无通路则不存在任何一条有限距离链能够从s经由边逐跳传播到v因此无论进行多少轮松弛v.d都停留在初始化时的∞。这一推论同时保证了Bellman-Ford 仅对可达顶点给出有意义的最短路径值不可达顶点保持∞是正确行为而非缺陷。4. 习题 24.1-3m 1 次提前终止的优化设m为所有u, v ∈ V中最短路径按权重计所含边数的最小值中的最大值。即使事先不知道m如何修改 Bellman-Ford 使其在m 1轮后终止4.1 标准算法的冗余轮次标准 Bellman-Ford 固定执行|V| - 1轮。由路径松弛性质可知从源点出发、最多含k条边的最短路径在第k轮松弛结束后必然已经达到最终最短路径权重再由上界性质之后的轮次中任何d值都不会再减小。因此若图中所有最短路径含边数不超过m则第m轮后全部d值已收敛第m 1轮必然无事可做。4.2 实现方法一轮无更新即停止由于事先不知道m不能精确地迭代恰好 m 次但可以这样实现记录本轮中v是否被relaxed即是否发生距离更新。若某一轮中没有任何顶点的d值被更新说明所有最短路径已经收敛立即终止算法。def bellman_ford_early_stop(G, w, s): # Initialize-Single-Source(G, s) d {v: float(inf) for v in G} pi {v: None for v in G} d[s] 0 for i in range(len(G) - 1): updated False for u, v in G.edges(): if d[v] d[u] w(u, v): d[v] d[u] w(u, v) pi[v] u updated True # 记录是否被更新 if not updated: # 一轮无更新 已经收敛 break # 在第 m1 轮提前终止 return d, pi由于第m轮后所有d值不再变化第m 1轮将检测不到任何更新算法随之终止——即使m未知也能在m 1轮内停住大幅减少实际迭代轮数。这在稀疏图中收益尤其明显例如仅由一条链构成的图m O(V)远小于|V| - 1的情形只是特例更常见的是m显著小于|V| - 1。5. 习题 24.1-4把负权回路影响标记为 -∞修改 Bellman-Ford使所有从源点出发路径上存在负权回路的顶点v满足d[v] -∞。负权回路意味着沿回路无限绕行可以让距离任意小因此这些顶点没有有限的最短路径。仓库给出的算法分两步正常执行|V| - 1轮松弛再做一轮检测若边(u, v)仍可松弛令d[v] -∞该顶点位于某负权回路上或其后继对每个d[v] -∞的顶点沿前驱链向上回溯把链上所有顶点也标记为-∞因为这些顶点同样位于通向负权回路的路径上。def follow_and_mark_pred(v, d, pi): 从负权回路可达点沿前驱链向上标记 if pi[v] is not None and d[pi[v]] ! -float(inf): d[pi[v]] -float(inf) follow_and_mark_pred(pi[v], d, pi) def bellman_ford_new(G, w, s): # Initialize-Single-Source(G, s) d {v: float(inf) for v in G} pi {v: None for v in G} d[s] 0 for i in range(len(G) - 1): for u, v in G.edges(): if d[v] d[u] w(u, v): d[v] d[u] w(u, v) pi[v] u # 第 |V| 轮仍可松弛 负权回路可达 for u, v in G.edges(): if d[v] d[u] w(u, v): d[v] -float(inf) # 沿前驱链回溯标记 for v in G: if d[v] -float(inf): follow_and_mark_pred(v, d, pi) return d, pi正确性直觉第|V|轮检测到的可松弛边(u, v)必然位于或指向负权回路而负权回路上的顶点在最后一轮松弛时其π仍会被更新为回路内的点参见习题 24.1-6因此沿π链回溯可以把整条通向负权回路的路径完整标记出来。6. 习题 24.1-5求解 δ*(v) min{δ(u, v)} 的 O(VE) 算法设δ(u, v)为顶点u到v的最短路径权重给出求δ\*(v) min_{u∈V} {δ(u, v)}即以任意顶点为源点时到达v的最短距离下界的O(VE)算法。仓库解答的前提是图中不存在负权回路。6.1 修改 RELAX把任意源点纳入松弛标准松弛只考虑一条路径的延续。这里我们把每个顶点本身也当作潜在源点修改松弛为MOD_RELAX(u, v, w) min w(u, v) ((u.d 0) ? u.d : 0) if v.d min v.d min即更新v.d时同时考虑两种情况u就是源点此时路径起点贡献为 0等价于以u.d是否小于 0 来决定是否累加或者u只是某条最短路径上的中间结点累加u.d。6.2 运行修改后的 Bellman-FordMOD_BELLMAN_FORD(G, w) for each v ∈ G.V v.d Infinity for i 1 to |G.V| - 1 for each edge (u, v) ∈ G.E MOD_RELAX(u, v, w)初始化时所有顶点均为∞即所有顶点都视为潜在源点经过O(VE)的松弛后v.d即所求δ\*(v)。运行时间显然为O(VE)与标准 Bellman-Ford 同阶这正是本解法的价值在不增加渐进复杂度的前提下一次性得到全源取最小的信息。7. 习题 24.1-6高效列出负权回路上的顶点给定带负权回路的加权有向图G给出一个列出其中一个负权回路全部顶点的高效算法并证明其正确性。7.1 算法仓库解答的思路极为简洁在 Bellman-Ford 的第|V|轮检测中找到负权回路上的一个顶点即最后一轮仍可被松弛的边(u, v)的某个端点从该点出发顺着前驱π逆向遍历即可得到负权回路。def find_negative_cycle(G, w, s): # 1) 标准 Bellman-Ford|V|-1 轮松弛 d, pi run_bellman_ford(G, w, s) # 2) 第 |V| 轮找到仍可松弛的边 for u, v in G.edges(): if d[v] d[u] w(u, v): # 3) 从 v 出发沿 π 链回溯直至回到 v 自身 cycle [] x v while True: cycle.append(x) x pi[x] if x v or x is None: break return list(reversed(cycle)) # 即负权回路 return None # 无负权回路7.2 正确性证明关键观察由于负权回路的存在Bellman-Ford 的松弛过程中一定会反复松弛回路上的所有边——每多一轮回路顶点沿环走一圈后距离又变小于是又被松弛。因此在算法结束时即第|V|轮检测时负权回路上每个顶点的前驱π都必然是回路内的点否则该顶点无法持续获得更小的距离值。于是从最后一轮仍可松弛的边(u, v)的端点出发沿π链回溯由于链上的顶点不断向后跳转且都位于同一负权回路内回溯过程必然在有限步内重新回到出发点形成一个闭合环路。该环的权重为负这正是它不断被松弛的原因即为所求的负权回路。这一技术在后文差分约束系统的不可行性判断24.4.md 习题 24.4-2 中x4 → x2 → x3 → x5 → x1 → x4 形成负权回路故无解的判定中直接复用。8. 延伸Bellman-Ford 思想在仓库中的其他落点本仓库以Solutions to Introduction to Algorithms为主题Bellman-Ford 的松弛思想贯穿全书多个章节可在阅读本节后顺藤摸瓜差分约束系统24.4.md把形如xi - xj ≤ bk的不等式组映射为约束图以虚拟顶点v0与所有顶点连权重 0 的边为源运行 Bellman-Ford有负权回路即无可行解24.4-2无回路时最短距离即为一组可行解且该解最大化了x1 x2 ... xn24.4-8还可最小化max{xi} - min{xi}用于施工调度排程24.4-9。其中 24.4-5 的优化——去掉v0并直接初始化d[v] 0——正是本节提前终止/去冗余思想的姊妹版本。矩阵乘法视角25.1.md单源最短路径可表达为向量 × 权重矩阵的广义矩阵乘积该乘积的逐列运算与 Bellman-Ford 第 3、4 行对边(?, i)的松弛一一对应从而把单源问题纳入全源最短路径Floyd-Warshall 等见 C25-All-Pairs-Shortest-Paths/README.md的统一框架。负权不可用场景的对照当边权非负时优先选择 Dijkstra24.3.md 习题 24.3-2 专门分析了负边权如何破坏其贪心证明O(E log V)优于 Bellman-Ford 的O(VE)。9. 小结与自测清单回到 24.1.md本节 6 道习题实际上覆盖了 Bellman-Ford 的完整知识闭环习题核心能力关键技术24.1-1手工推演松弛、识别负权回路逐轮追踪d/π第 |V| 轮检测24.1-2理解不可达顶点无通路则无法松弛d保持 ∞24.1-3提前终止优化一轮无更新即停m 1轮收敛24.1-4标记负权回路影响域检测 沿π链回溯标记-∞24.1-5推广任意源点最短距离下界修改 RELAXO(VE)24.1-6输出负权回路顶点沿π逆向遍历成环建议的验证方式任选一个小型带权有向图先手工按 24.1-1 的方式逐轮写出d与π再对照第 2 节的表格格式自检随后人为制造一条负权回路用第 7 节的回溯法验证能否正确列出回路顶点。把本节松弛—收敛—检测的三段式理解牢固掌握后再进入 24.4.md 的差分约束与后续全源最短路径章节会顺畅得多。赞分享文档教程示例工程【免费下载链接】CLRS:notebook:Solutions to Introduction to Algorithms项目地址https://gitcode.com/gh_mirrors/cl/CLRS点击查看免费下载相关推荐Cytoscape.js Bellman-Ford 算法实战最短路径计算与负权环检测Cytoscape.js Bellman Ford 算法实战最短路径计算与负权环检测 eles.bellmanFord 是 Cytoscape.js 在集合数据可视化cp-algorithms 详解 Bellman-Ford 算法负权边单源最短路、负环检测与最短路径还原cp algorithms 详解 Bellman Ford 算法负权边单源最短路、负环检测与最短路径还原 Bellman Ford贝尔曼 福特算法是经典的文档教程知识库NPU与CPU双平台部署nest_base_jx.goog_in1k环境配置与性能对比实测NPU与CPU双平台部署nest_base_jx.goog_in1k环境配置与性能对比实测 nest_base_jx.goog_in1k是一个基于Huggin上一篇Taste-Skill 实战指南让 AI 生成的 React、Vue、Svelte 前端摆脱模板脸下一篇OpenSpeedy快捷键冲突检测器自动分析工具的终极指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考