知识卡片

普通读书笔记卡 · 3645.e.1

DAG拓扑序松弛每边一次

理解等级:中级
  1. 先拓扑排序并初始化,
  2. 再依拓扑序处理每个顶点,对其所有出边松弛一次。

每条最短路径上的边必按路径方向被松弛;总时间 Θ(V+E)。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      The DAG-SHORTEST-PATHS procedure makes just one pass over the vertices in the topologically sorted order. As it processes each vertex, it relaxes each edge that leaves the vertex. Figure 22.5 shows the execution of this

    参考来源

    - 位置:《算法导论(第4版)》第22章《单源最短路径》(OEBPS/chapter022.xhtml,文本字符[25000,30000))。 - 结论依据:伪代码和定理22.5利用拓扑序保证路径松弛顺序并给出线性成本。 - 原始内容:The D AG -S HORTEST -P ATHS procedure makes just one pass over the vertices in the topologically sorted order. As it processes each vertex, it relaxes each edge that leaves the vertex. Figure 22.5 shows the execution of this