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

Question

我读过这个post 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)

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

How to take into account the minimum value vertex in Dijsktra algorithm?

dijkstra