Dijkstra's Algorithm for SSSP
Let G be a directed graph, s a node of G,
and cost a cost function on the edges of G .
A single source shortest path algorithm computes the shortest paths
from s to all other nodes of G with respect
to cost .
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 nonnegative edge costs.
DIJKSTRA_T() is a template function. The template parameter
NT can be instantiated with any number
type.
Example of How to
Use DIJKSTRA_T()
DIJKSTRA() is the name of the preinstantiated versions
of DIJKSTRA_T() . There is one function DIJKSTRA()
for edge costs of type int and one for double .
Example of How to Use
DIJKSTRA()
Important Notice: 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 DIJKSTRA_T()
with one of the LEDA number types.
Running time
The running time of DIJKSTRA_T() and DIJKSTRA()
for a graph G=(V,E) is O(E+VlogV) .
Tips

See also:
Shortest Path Algorithms
Checking the Results of an SSSP Algorithm
Generic Algorithms for SSSP
SSSP Algorithm for Acyclic Graphs
BellmanFord Algorithm for SSSP
Number Types
Graphs and Related Data Types
Graph Algorithms
Manual Entries:
Manual
Page Shortest Path Algorithms
