知识卡片

普通读书笔记卡 · 3645.i.1.a

重赋权保留最短路径

理解等级:中级

Johnson 先把可能为负的边权重赋为非负,再逐源运行 Dijkstra。

重赋权必须同时保证任意两点的最短路径选择不变,且每条新边权非负;若存在负环则报告失败。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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