知识卡片
DAG拓扑序松弛每边一次
- 先拓扑排序并初始化,
- 再依拓扑序处理每个顶点,对其所有出边松弛一次。
每条最短路径上的边必按路径方向被松弛;总时间 Θ(V+E)。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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