CODEWITHSUNDEEP
algorithm
jay
jay

Reputation: 99

Running time for Dijkstra's algorithm on a priority queue implemented by sorted list/array

So I'm curious to know what the running time for the algorithm is on on priority queue implemented by a sorted list/array. I know for an unsorted list/array it is O((n^2+m)) where n is the number of vertices and m the number of edges. Thus that equates to O(n^2) time. But would it be faster if i used an sorted list/array...What would the running time be? I know extractmin would be constant time.

Upvotes: 5

Views: 5886

Answers (2)

Kirill Chilingarashvili
Kirill Chilingarashvili

Reputation: 1089

I use SortedList http://blog.devarchive.net/2013/03/fast-dijkstras-algorithm-inside-ms-sql.html It is faster about 20-50 times than sorting List once per iteration

Upvotes: 0

Rubys
Rubys

Reputation: 3207

Well, Let's review what we need for dijkstra's algorithm(for future reference, usually vertices and edges are used as V and E, for example O(VlogE)):
Merging together all the sorted adjacency lists: O(E)
Extract Minimum : O(1)
Decrease Key : O(V)
Dijkstra uses O(V) extract minimum operations, and O(E) decrease key operations, therefore:
O(1)*O(V) = O(V)
O(E)*O(V) = O(EV) = O(V^2)
Taking the most asymptotically significant portion:
Eventual asymptotic runtime is O(V^2).
Can this be made better? Yes. Look into binary heaps, and better implementations of priority queues.

Edit: I actually made a mistake, now that I look at it again. E cannot be any higher than V^2, or in other words E = O(V^2).
Therefore, in the worst case scenario, the algorithm that we concluded runs in O(EV) is actually O(V^2 * V) == O(V^3)

Upvotes: 5

Related Questions