知识卡片

普通读书笔记卡 · 3645.a.3

可达负环使最短权无下界

理解等级:中级

从源点可达的负权环若位于到目标的可达路线上,可重复绕环让路径权重无限降低,此时目标最短路权记为−∞。

不可达负环不影响该源点的问题。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第22章 单源最短路径 · 查看原书依据

      If the graph contains a negative-weight cycle reachable from s, however, shortest-path weights are not well defined. No path from s to a vertex on the cycle can be a shortest path—you can always find a path with lower

    参考来源

    - 位置:《算法导论(第4版)》第22章《单源最短路径》(OEBPS/chapter022.xhtml,文本字符[5000,10000))。 - 结论依据:原文区分可达负环、其后继与不可达负环;图22.1标明−∞和∞。 - 原始内容:If the graph contains a negative-weight cycle reachable from s , however, shortest-path weights are not well defined. No path from s to a vertex on the cycle can be a shortest path—you can always find a path with lower