知识卡片
BF复杂度依图表示
以邻接表逐轮找全部边,原书给出 O(V²+VE),当 E=Ω(V) 时写为 O(VE)。
直接边列表可避免每轮扫描空邻接表的额外 V 项。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第22章 单源最短路径 · 查看原书依据
In the frequent case where |E| = Ω(V), we can express this running time as O(VE). Exercise 22.1-5 asks you to make the Bellman-Ford algorithm run in O(VE) time even when |E| = o(V). To prove the correctness of the
参考来源
- 位置:《算法导论(第4版)》第22章《单源最短路径》(OEBPS/chapter022.xhtml,文本字符[20000,25000))。
- 结论依据:原文区分邻接表扫描成本与常见 E=Ω(V) 的简化条件。
- 原始内容:In the frequent case where | E | = Ω( V ), we can express this running time as O ( VE ). Exercise 22.1-5 asks you to make the Bellman-Ford algorithm run in O ( VE ) time even when | E | = o ( V ). To prove the correctness of the