Dijkstra's Algorithm for SSSP
G be a directed graph,
s a node of
cost a cost function on the edges of
A single source shortest path algorithm computes the shortest paths
s to all other nodes of
G with respect
Remark: Finding the shortest path from one node to one other
node is not significantly faster than computing the shortest paths from
the source to all other nodes.
DIJKSTRA_T() is the LEDA function for computing single
source shortest paths in a directed graph with non-negative edge costs.
DIJKSTRA_T() is a template function. The template parameter
NT can be instantiated with any number
Example of How to
DIJKSTRA() is the name of the preinstantiated versions
DIJKSTRA_T(). There is one function
for edge costs of type
int and one for
Example of How to Use
DIJKSTRA() only performs correctly
if all arithmetic is performed without rounding errors and without overflows.
If you are not sure about this, you should use
with one of the LEDA number types.
The running time of
for a graph
G=(V,E) is O(|E|+|V|log|V|) .
Shortest Path Algorithms
Checking the Results of an SSSP Algorithm
Generic Algorithms for SSSP
SSSP Algorithm for Acyclic Graphs
Bellman-Ford Algorithm for SSSP
Graphs and Related Data Types
Page Shortest Path Algorithms