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

Posted by jay on Stack Overflow See other posts from Stack Overflow or by jay
Published on 2010-04-21T04:39:58Z Indexed on 2010/04/21 4:43 UTC
Read the original article Hit count: 444

Filed under:

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.

© Stack Overflow or respective owner

Related posts about algorithm