Shortest Path AlgorithmsGiven a directed graph with costs on the edges, it is a very natural and basic question to ask for the minimum length path from one node to another node, or between certain pairs of nodes. The length of a path is the sum of the costs of the edges. The Number Type for the Edge CostsAll functions in this section are template functions. The template parameter
The reason why we did not restrict our algorithms to The LEDA Functions for Shortest PathsSingle Source Shortest Path (SSSP) Algorithms compute shortest paths from one source node to all other nodes in a graph. LEDA provides:
All Pairs Shortest Paths Algorithms compute shortest paths between all pairs of nodes in a graph. Remark: The graph algorithms in LEDA are generic, that is, they accept graphs as well as parameterized graphs. |
See also:Manual Entries: |