Search code examples
algorithmqueuebig-odijkstraheap

Execution time of Dijkstra's algorithm using a heap-based priority queue

I don't understand why the execution order is O(m log n) instead of O(nm log n) when using a heap-based priority queue.

The WHILE have to process n nodes and evaluate all m graph's edges and in worst case the algorithm have to relax d(v) (or v.distance) for every edge what takes O(log n) for each one, so it would be O(nm log n)

pseudocode

PD: Sorry for my bad English.

Solution

  • You're right that the while loop will visit every node and every edge, and each heap operation takes time O(log n), but that doesn't mean that the total work done is O(mn log n).

    Specifically, each iteration of the loop focuses on some node v. When node v is processed, we visit each outgoing edge from v do O(log n) work for each of those edges. If we number the nodes of the graph v1, v2, ..., vn and denote the degree of node vi (the number of edges it touches) as deg(vi), this means that across all iterations of the loop the work we do is

    O(log n) · (deg(v1) + deg(v2) + ... + deg(vn)).

    The handshaking lemma says that the inner sum is equal to 2m, since each edge is counted twice. This means that the total work done works out to 2m · O(log n) = O(m log n).