SSSP Algorithms for Acyclic Graphs
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.
ACYCLIC_SHORTEST_PATH_T() is the LEDA function for
computing single source shortest paths in a directed acyclic graph. ACYCLIC_SHORTEST_PATH_T()
is a template function. The template parameter NT can be
instantiated with any number type.
Example
of How to Use ACYCLIC_SHORTEST_PATH_T()
ACYCLIC_SHORTEST_PATH() is the name of the preinstantiated
versions of ACYCLIC_SHORTEST_PATH_T(). There is one function
ACYCLIC_SHORTEST_PATH() for edge costs of type int
and one for double.
Example
of How to Use ACYCLIC_SHORTEST_PATH()
Important Notice: ACYCLIC_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 ACYCLIC_SHORTEST_PATH_T()
with one of the LEDA number types.
Running time
The running time of ACYCLIC_SHORTEST_PATH_T() and ACYCLIC_SHORTEST_PATH()
for a graph G=(V,E) is linear in the size of the graph (O(|V|+|E|)).
Tips
|