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

### Tips

• If your graph is acyclic, use `ACYCLIC_SHORTEST_PATH_T()`.
• If you know that there can be no overflows and no rounding errors you can use `ACYCLIC_SHORTEST_PATH().`
• The Generic Algorithms for SSSP provide a convenient interface to all SSSP algorithms in LEDA. You do not have to think about cycles and negative edge costs beforehand.
• If your edge costs are non-negative, you can also call Dijkstra's Algorithm for SSSP directly.
• If your graph contains cycles and there are edges with negative costs, you can also call the Bellman-Ford Algorithm for SSSP directly.
• LEDA also provides functions for checking the results of an SSSP Algorithm.

Shortest Path Algorithms

Generic Algorithms for SSSP

Dijkstra's Algorithm for SSSP

Number Types

Graphs and Related Data Types

Graph Algorithms

Manual Entries: