Algorithmic Solutions > LEDA > LEDA Guide > Graph Algorithms > Shortest Path Algorithms

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:

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


Parameterized Graphs

Manual Entries:

Manual Page Shortest Path Algorithms

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