(algorithm)
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 ...)
Johnson's algorithm.
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].
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 20 September 2006.
HTML page formatted Wed Mar 13 12:42:45 2019.
Cite this as:
Paul E. Black, "Dijkstra's algorithm", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 20 September 2006. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/dijkstraalgo.html