知识卡片
可达负环使最短权无下界
从源点可达的负权环若位于到目标的可达路线上,可重复绕环让路径权重无限降低,此时目标最短路权记为−∞。
不可达负环不影响该源点的问题。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 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