Definition: An algorithm to find the shortest paths from a single source vertex to all other vertices in a weighted, directed graph. All weights must be nonnegative.
Aggregate parent (I am a part of or used in ...)
Aggregate child (... is a part of or used in me.)
priority queue, greedy algorithm.
See also Bellman-Ford algorithm, all pairs shortest path.
Note: A naive implementation of the priority queue gives a run time complexity O(V²), where V is the number of vertices. Implementing the priority queue with a Fibonacci heap makes the time complexity O(E + V log V), where E is the number of edges.
After [CLR90, page 527].
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 20 September 2006.
HTML page formatted Mon Nov 18 10:44:09 2013.
Cite this as:
Paul E. Black, "Dijkstra's algorithm", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 20 September 2006. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/dijkstraalgo.html