Time complexity of Dijkstra's Algorithm

general
,
1

I coded up an implementation of Dijkstra’s Algorithm.It works correctly as I had coded from a pseudocode which was very abstract for a MOOC,6 months back.
However,I wanted to know what is its running time complexity.I’m doubtful if its even O(V^2).As the graph was just of 200 vertices.I don’t know about the edges though.
Here’s the code:


[1]
And here's the [data][2] 
I think its O(V^2*E).Though I'm not sure.    

   


 


  [1]: http://pastebin.com/SkHMzkaC
  [2]: http://pastebin.com/GxF2evc7
2

Hello,

The time complexity partially depends on the algorithm’s implementation.

As stated on Wikipedia, the worst case performance is achieved by a min-priority queue implemented by a Fibonacci heap, which runs in O(|E| + |V|log |V|).

However, Dijkstra’s original implementation ran in O(|V|^2).

You can read more here.

Best regards,

Bruno

3

@kuruma could u tell me what is the order of my dijkstra implementation?
I just wanna confirm it whether I’ve calculated it correctly or not.

4

By looking at your code, it seems to be as you’ve indicated above :slight_smile:

1 Like