Shortest Path Algorithms
Given 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 Costs
All 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 Paths
Single 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.