7.21.Dijkstra算法分析 - Python 数据结构

返回介绍

7.21.Dijkstra算法分析

发布于 2019-08-07 字数 547 浏览 745 评论 0

7.21.Dijkstra算法分析

最后,让我们看看 Dijkstra 算法的运行时间。我们首先注意到,构建优先级队列需要 $$O(V)$$ 时间,因为我们最初将图中的每个顶点添加到优先级队列。 一旦构造了队列,则对于每个顶点执行一次 while 循环,因为顶点都在开始处添加,并且在那之后才被移除。 在该循环中每次调用 delMin,需要 $$O(logV)$$时间。 将该部分循环和对 delMin 的调用取为 $$O(Vlog(V))$$。 for 循环对于图中的每个边执行一次,并且在 for 循环中,对 decreaseKey 的调用需要时间 $$O(Elog(V))$$ 。 因此,组合运行时间为 $$O((V + E)log(V))$$。

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

支持 Markdown 语法,需要帮助?

目前还没有任何评论,快来抢沙发吧!