(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
An animation illustrating Dijkstra's algorithm.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 15 May 2024.
HTML page formatted Wed Aug 14 14:11:53 2024.
Cite this as:
Paul E. Black, "Dijkstra's algorithm", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 15 May 2024. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/dijkstraalgo.html