知识卡片

普通读书笔记卡 · 3645

最短路分单源与全点对

理解等级:初级

带权图的最短路径可按查询范围区分:

  • 单源问题求指定起点到所有顶点的路径,
  • 全点对问题求每一对顶点间的路径。

两者输入范围和输出规模不同,不能将单源运行一次就当作全点对结果。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第六部分 图算法 · 查看原书依据

      Chapters 22 and 23 consider how to compute shortest paths between vertices when each edge has an associated length or “weight.” Chapter 22 shows how to find shortest paths from a given source vertex to all other vertices, and Chapter 23 examines methods to compute shortest paths between every pair of vertices.

    参考来源

    - 位置:《算法导论(第4版)》第六部分引言《图算法》(OEBPS/part006.xhtml,文本字符[0,3106))。 - 结论依据:原文并列介绍单源和所有顶点对的最短路径任务。 - 原始内容:Chapters 22 and 23 consider how to compute shortest paths between vertices when each edge has an associated length or “weight.” Chapter 22 shows how to find shortest paths from a given source vertex to all other vertices, and Chapter 23 examines methods to compute shortest paths between every pair of vertices.