知识卡片

普通读书笔记卡 · 5654.d.1.f.4.i · 生成模型:未记录

重复松弛检测可达负环

理解等级:中级

初始化源点为0、其余为无穷;最多进行 V−1 轮边松弛,每轮按 dist[u]+w(u,v) 改善 dist[v],若某轮无变化可提前停止。再检查一轮,如果仍可从有限距离继续松弛,说明存在从源点可达的负环;仅影响能从该负环到达的目标的最短距离。

无穷距离不能直接参与算术,尤其无穷加负权可能被误当成有限路径。图03302–03304未先检查不可达起点,不能可靠检测源点可达性;中间加法与写回也需检查范围。标准实现时间 O(VE),前驱可重建有限最短路径。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      Bellman-Ford(如图6-16和例6-6所示)可以在不存在负值环的情况下使用。也就是说,不存在一个环,其边权值总和为负数。在这样的环存在的情况下,“最短路径”的概念是没有意义的。虽然图6-13包含一个环{1,3,2},但是边权值为正,所以Bellman-Ford和Dijkstra算法都能够适

    参考来源

    - 位置:《算法技术手册》第6章《变种》(spine1578;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1541.html;u164-ch06-010)。 - 结论依据:164全文、03301–03305伪代码、完整实现和示例实读。 - 原始内容:Bellman-Ford(如图6-16和例6-6所示)可以在不存在负值环的情况下使用。也就是说,不存在一个环,其边权值总和为负数。在这样的环存在的情况下,“最短路径”的概念是没有意义的。虽然图6-13包含一个环{1,3,2},但是边权值为正,所以Bellman-Ford和Dijkstra算法都能够适