Algorithmic Solutions > LEDA > LEDA Guide > Graph Algorithms > Shortest Path Algorithms > SSSP Algorithms for Acyclic Graphs

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|)).


See also:

Shortest Path Algorithms

Generic Algorithms for SSSP

Dijkstra's Algorithm for SSSP

Bellman-Ford Algorithm for SSSP

Checking the Results of an SSSP Algorithm

Number Types

Graphs and Related Data Types

Graph Algorithms

Manual Entries:

Manual Page Shortest Path Algorithms

Please send any suggestions, comments or questions to
© Copyright 2001-2003, Algorithmic Solutions Software GmbH