0

I have read this post Understanding Time complexity calculation for Dijkstra Algorithm to understand the complexity of Dijkstra algorithm. However, I can't see where the time to pick at each iteration the minimum value vertex (the one whose value will be fixed after this iteration) inside the heap is involved in the calculus... Could someone clearly explain me where it is involved ?

Thanks !

MysteryGuy
  • 1,091
  • 2
  • 18
  • 43

1 Answers1

0

Dijkstra algorithm is something like this

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)

The first cycle makes V iterations and the second makes sum of degrees of all vertices iterations, so it's 2 * E or O(E) iterations. Total complexity is O(VlogV + ElogV)

Livace
  • 126
  • 7