知识卡片

普通读书笔记卡 · 3645.d.1.b.3

BF复杂度依图表示

理解等级:中级

以邻接表逐轮找全部边,原书给出 O(V²+VE),当 E=Ω(V) 时写为 O(VE)。

直接边列表可避免每轮扫描空邻接表的额外 V 项。

这张卡片看不懂?

已有反馈 · 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