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 non-negative 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|+|V|log|V|) .
Tips
|
See also:
Shortest Path Algorithms
Checking the Results of an SSSP Algorithm
Generic Algorithms for SSSP
SSSP Algorithm for Acyclic Graphs
Bellman-Ford Algorithm for SSSP
Number Types
Graphs and Related Data Types
Graph Algorithms
Manual Entries:
Manual
Page Shortest Path Algorithms
|