知识卡片

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

斐波那契堆版最短路成本

理解等级:中级

斐波那契堆把降键摊还成本降为 O(1),提取最小仍为 O(lg V),于是总时间 O(E+V lg V)。这是针对大量边松弛时降键成本的改进。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      By implementing the min-priority queue with a Fibonacci heap (see page 478), you can improve the running time to O(V lg V + E). The amortized cost of each of the |V| EXTRACT-MIN operations is O(lg V), and each D

    参考来源

    - 位置:《算法导论(第4版)》第22章《单源最短路径》(OEBPS/chapter022.xhtml,文本字符[40000,45000))。 - 结论依据:原文对两类堆的摊还操作成本和总时间进行对比。 - 原始内容:By implementing the min-priority queue with a Fibonacci heap (see page 478), you can improve the running time to O ( V lg V + E ). The amortized cost of each of the | V | E XTRACT -M IN operations is O (lg V ), and each D