知识卡片
重赋权保留最短路径
Johnson 先把可能为负的边权重赋为非负,再逐源运行 Dijkstra。
重赋权必须同时保证任意两点的最短路径选择不变,且每条新边权非负;若存在负环则报告失败。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第23章 所有结点对的最短路径 · 查看原书依据
Johnson’s algorithm uses the technique of reweighting, which works as follows. If all edge weights w in a graph G = (V, E) are nonnegative, Dijkstra’s algorithm can find shortest paths between all pairs of vertices by
参考来源
- 位置:《算法导论(第4版)》第23章《所有结点对的最短路径》(OEBPS/chapter023.xhtml,文本字符[25000,30000))。
- 结论依据:原文列出重赋权两项条件及 Bellman-Ford、Dijkstra 两个子过程。
- 原始内容:Johnson’s algorithm uses the technique of reweighting , which works as follows. If all edge weights w in a graph G = ( V , E ) are nonnegative, Dijkstra’s algorithm can find shortest paths between all pairs of vertices by