Algorithmic Solutions > LEDA > LEDA Guide > Graph Algorithms > Shortest Path Algorithms > All Pairs Shortest Paths Algorithms

All Pairs Shortest Paths Algorithms

Let G be a directed graph and cost a cost function on the edges of G. Edge costs may be positive or negative. An all pairs source shortest paths algorithm computes the shortest paths between all pairs of nodes in G with respect to cost.

ALL_PAIRS_SHORTEST_PATHS_T() is the LEDA function for computing the lengths of the shortest paths between all pairs of nodes in a directed graph. ALL_PAIRS_SHORTEST_PATHS_T() is a template function. The template parameter NT can be instantiated with any number type.

Example of How to Use ALL_PAIRS_SHORTEST_PATHS_T()

ALL_PAIRS_SHORTEST_PATHS() is the name of the preinstantiated versions of ALL_PAIRS_SHORTEST_PATHS_T(). There is one function ALL_PAIRS_SHORTEST_PATHS() for edge costs of type int and one for double.

Example of How to Use ALL_PAIRS_SHORTEST_PATHS()

Important Notice: ALL_PAIRS_SHORTEST_PATHS() only performs correctly if all arithmetic is performed without rounding errors and without overflows. If you are not sure about this, you should use ALL_PAIRS_SHORTEST_PATHS_T() with one of the LEDA number types.

Running time

The running time of ALL_PAIRS_SHORTEST_PATHS_T() and ALL_PAIRS_SHORTEST_PATHS() for a graph G=(V,E) is O(|V||E|+|V|2log|V|).

See also:

Shortest Path Algorithms


Number Types

Graphs and Related Data Types

Graph Algorithms


Manual Entries:

Manual Page Shortest Path Algorithms




Please send any suggestions, comments or questions to leda@algorithmic-solutions.com
© Copyright 2001-2003, Algorithmic Solutions Software GmbH