如何在Dijkstra算法中考虑最小值顶点？

Question

我已经阅读了这篇文章Understanding Time complexity calculation for Dijkstra Algorithm来了解Dijkstra算法的复杂性。但是，我无法看到在每次迭代中选择最小值顶点（在迭代后其值将被修复的那个）的时间在堆中的时间参与微积分......有人可以清楚地解释我它在哪里参与？

谢谢 ！

Answer 1

Dijkstra算法是这样的

repeat V times:
    take min from heap; // Works in O(1)
    erase min from heap; // Works in O(log V)
    for vertices connected with current:
        update distance; // Works in O(1)
        update value in heap; // Works in O(log V)

第一个循环使V迭代，第二个循环使所有顶点迭代的度数之和，所以它是2 * E或O(E)迭代。总复杂性是O(VlogV + ElogV)