Dijkstra's algorithm: Difference between revisions

Revision as of 00:23, 22 April 2004

Revision as of 00:38, 22 April 2004

Line 40:

Dijkstra's algorithm can be implemented efficiently by storing the graph in the form of adjacency lists and using a [[Fibonacci heap]] as [[priority queue]] to implement the Extract-Min function.

If the graph has ''m'' edges and ''n'' vertices, then the algorithm's time requirements are Θ(''m'' + ''n'' log ''n'') (see [[Big O notation]]), assuming that comparisons of edge weights take constant time.