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 NT can be instantiated with any number type. Additionally, there are preinstantiated versions for int and double. The names of the template functions have suffix _T and the functions without suffix _T are the preinstantiated versions

The reason why we did not restrict our algorithms to int and double is that the number types int, float, and double provided by C++ are only crude approximations of the mathematical counterparts: ints can overflow, the arithmetic for floats and doubles incurs rounding errors. The functions in this section only perform correctly if all arithmetic is performed without rounding errors.

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:

• Generic Algorithms for SSSP
• Checking the Results of an SSSP Algorithm
• SSSP Algorithms for Acyclic Graphs
• Dijkstra's Algorithm for SSSP for problems with non-negative edge costs.
• Bellman-Ford Algorithm for SSSP

All Pairs Shortest Paths Algorithms compute shortest paths between all pairs of nodes in a graph.

Minimum Cost Ratio Cycle

Remark: The graph algorithms in LEDA are generic, that is, they accept graphs as well as parameterized graphs.

See also:

Graph Algorithms

Graphs and Related Data Types

Number Types

Graphs

Parameterized Graphs

Manual Entries:

Manual Page Shortest Path Algorithms