Here's my attempt:

Initialisation -

  For initialisation of distance array - O(V)
  Priority Queue creation - O(V) ('cause all distances except the 
                  starting vertex is Infinity)

Running -

  Extract min - O(V)
  To check for all neighbours for all vertices total - O(E) * time to 
                  update it's new position in PQ.(here's my doubt)

In my textbook, the time to update it's new position in PQ is taken to be O(1), why?

For a single update -

  Time to find the node which is to be updated, as I don't have a 
  pointer to it, which is O(V).

So total time complexity should be - $O(E*V+{V}^2)$ instead of $O(E+{V}^2)$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.