Generic Algorithms for SSSP
Let G be a directed graph, s a node of G,
and cost a cost function on the edges of G .
Edge costs may be positive or negative. 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.
SHORTEST_PATH_T() is the generic LEDA function for
computing single source shortest paths in a directed graph. SHORTEST_PATH_T()
is a template function. The template parameter NT can be
instantiated with any number type.
Example of How
to Use SHORTEST_PATH_T()
SHORTEST_PATH() is the name of the preinstantiated
versions of SHORTEST_PATH_T() . There is one function SHORTEST_PATH()
for edge costs of type int and one for double .
Example of How
to Use SHORTEST_PATH()
Important Notice: SHORTEST_PATH() only performs correctly
if all arithmetic is performed without rounding errors and without overflows.
If you are not sure about this, you should use SHORTEST_PATH_T()
with one of the LEDA number types.
Running time
The running time of SHORTEST_PATH_T() and SHORTEST_PATH()
for a graph G=(V,E) is
 linear in the size of the graph (O(V+E)) for acyclic graphs
 O(E+VlogV) if all edge costs are nonnegative
 O(VE) otherwise
Tips

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