Question

7.21.Dijkstra算法分析

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