7.21. Dijkstra算法分析

7.21. Analysis of Dijkstra’s Algorithm

中文英文

最后，让我们来看看 Dijkstra 算法的运行时间。我们首先注意到，构建优先队列需要 $O(|V|)$ 时间，因为我们最初将图中的每个节点都添加到优先队列中。一旦队列构建完成，while 循环会对每个节点执行一次，因为节点在开始时都已添加，并且之后才会被移除。在这个循环中，每次调用 delete 需要 $O(\log |V|)$ 时间。综合来看，这部分循环和调用 delete 的时间复杂度是 $O(|V|\times \log |V|)$。for 循环对图中的每条边执行一次，而在 for 循环中，调用 change_priority 需要 $O(|E|\times \log |V|)$ 时间。因此，总体运行时间是 $O((|V|+|E|)\times \log |V|)$。

Finally, let’s look at the running time of Dijkstra’s algorithm. We first note that building the priority queue takes $O(|V|)$ time since we initially add every vertex in the graph to the priority queue. Once the queue is constructed, the while loop is executed once for every vertex since vertices are all added at the beginning and only removed after that. Within that loop each call to delete takes $O(\log |V|)$ time. Taken together, that part of the loop and the calls to delete take $O(|V|\times \log |V|)$. The for loop is executed once for each edge in the graph, and within the for loop the call to change_priority takes $O(|E|\times \log |V|)$ time. So the combined running time is $O((|V|+|E|)\times \log |V|)$.

---

最后更新: 2024年9月13日
创建日期: 2024年9月9日