Next: Maximum Flow ( max_flow Up: Graph Algorithms Previous: Basic Graph Algorithms ( Contents Index

Shortest Path Algorithms ( shortest_path )

Let G be a graph, s a node in G, and c a cost function on the edges of G. Edge costs may be positive or negative. For a node v let $\mu$ (v) be the length of a shortest path from s to v (more precisely, the infimum of the lengths of all paths from s to v). If v is not reachable from s then $\mu$ (v) = + $\infty$ and if v is reachable from s through a cycle of negative cost then $\mu$ (v) = - $\infty$ . Let V⁺, V^f, and V^- be the set of nodes v with $\mu$ (v) = + $\infty$ , - $\infty$ < $\mu$ (v) < + $\infty$ , and $\mu$ (v) = - $\infty$ , respectively.

The solution to a single source shortest path problem (G, s, c) is a pair (dist, pred) where dist is a node_array<NT> and pred is a node_array<edge> with the following properties. Let P = $\left\{\vphantom{\hspace{\setspacing} \mathit{pred}[\mathit{v}] \mbox{ ; } v \... ...nd } \mathit{pred}[\mathit{v}] \not= \mathit{nil} \hspace{\setspacing} }\right.$ pred[v] ; v $\in$ V and pred[v] $\not=$ nil $\left.\vphantom{\hspace{\setspacing} \mathit{pred}[\mathit{v}] \mbox{ ; } v \i... ...d } \mathit{pred}[\mathit{v}] \not= \mathit{nil} \hspace{\setspacing} }\right\}$ . A P-cycle is a cycle all of whose edges belong to P and a P-path is a path all of whose edges belong to P.

v $\in$ V⁺ iff v $\not=$ s and pred[v] = nil and v $\in$ V^f $\cup$ V^- iff v = s or pred[v] $\not=$ nil.
s $\in$ V^f if pred[s] = nil and s $\in$ V^- otherwise.
v $\in$ V^f if v is reachable from s by a P-path and s $\in$ V^f. P restricted to V^f forms a shortest path tree and dist[v] = $\mu$ (s, v) for v $\in$ V^f.
All P-cycles have negative cost and v $\in$ V^- iff v lies on a P-cycle or is reachable from a P-cycle by a P-path.

Most functions in this section are template functions. The template parameter NT can be instantiated with any number type. In order to use the template version of the function the .t-file

#include <LEDA/templates/shortest_path.t>

must be included. The functions are pre-instantiated with int and double. The function names of the pre-instantiated versions are without the suffix _T.

Special care should be taken when using the functions with a number type NT that can incur rounding error, e.g., the type double. The functions perform correctly if all arithmetic performed is without rounding error. This is the case if all numerical values in the input are integers (albeit stored as a number of type NT) and if none of the intermediate results exceeds the maximal integer representable by the number type (2⁵² in the case of doubles). All intermediate results are sums and differences of input values, in particular, the algorithms do not use divisions and multiplications. All intermediate values are bounded by nC where n is the number of nodes and C is the maximal absolute value of any edge cost.

bool SHORTEST_PATH_T(graph G, node s, edge_array<NT> c, node_array<NT>& dist, node_array<edge>& pred)

SHORTEST_PATH solves the single source shortest path problem in the graph G(V, E) with respect to the source node s and the cost-function given by the edge_array c.
The procedure returns false if there is a negative cycle in G that is reachable from s and returns true otherwise.
It runs in linear time on acyclic graphs, in time O(m + nlog n) if all edge costs are non-negative, and runs in time O(min(D, n)m) otherwise. Here D is the maximal number of edges on any shortest path.

node_array<int> CHECK_SP_T(graph G, node s, edge_array<NT> c, node_array<NT> dist, node_array<edge> pred)

checks whether the pair (dist, pred) is a correct solution to the shortest path problem (G, s, c) and returns a node_array<int> label with label[v] < 0 if v has distance - $\infty$ (-2 for nodes lying on a negative cycle and -1 for a node reachable from a negative cycle), label[v] = 0 if v has finite distance, and label[v] > 0 if v has distance + $\infty$ . The program aborts if the check fails. The algorithm takes linear time.

void ACYCLIC_SHORTEST_PATH_T(graph G, node s, edge_array<NT> c, node_array<NT>& dist, node_array<edge>& pred)

solves the single source shortest path problem with respect to source s. The algorithm takes linear time.
Precondition G must be acyclic.

void DIJKSTRA_T(graph G, node s, edge_array<NT> cost, node_array<NT>& dist, node_array<edge>& pred)

solves the shortest path problem in a graph with non-negative edges weights.
Precondition The costs of all edges are non-negative.

void DIJKSTRA_T(graph G, node s, edge_array<NT> cost, node_array<NT>& dist)

as above, but pred is not computed.

NT DIJKSTRA_T(graph G, node s, node t, edge_array<NT> c, node_array<edge>& pred)

computes a shortest path from s to t and returns its lenght. The cost of all edges must be non-negative. The return value is unspecified if there is no path from s to t. The array pred records a shortest path from s to t in reverse order, i.e., pred[t] is the last edge on the path. If there is no path from s to t or if s = t then pred[t] = nil. The worst case running time is O(m + nlog n), but frequently much better.

bool BELLMAN_FORD_B_T(graph G, node s, edge_array<NT> c, node_array<NT>& dist, node_array<edge>& pred)

BELLMAN_FORD_B solves the single source shortest path problem in the graph G(V, E) with respect to the source node s and the cost-function given by the edge_array c.
BELLMAN_FORD_B returns false if there is a negative cycle in G that is reachable from s and returns true otherwise. The algorithm ([9]) has running time O(min(D, n)m) where D is the maximal number of edges on any shortest path. The algorithm is only included for pedagogical purposes.

void BF_GEN(GRAPH<int,int>& G, int n, int m, bool non_negative = true)

generates a graph with at most n nodes and at most m edges. The edge costs are stored as edge data. The running time of BELLMAN_FORD_B on this graph is $\Omega$ (nm). The edge weights are non-negative if non_negative is true and are arbitrary otherwise.
Precondition m > = 2n and m < = n²/2.

bool BELLMAN_FORD_T(graph G, node s, edge_array<NT> c, node_array<NT>& dist, node_array<edge>& pred)

BELLMAN_FORD_T solves the single source shortest path problem in the graph G(V, E) with respect to the source node s and the cost-function given by the edge_array c.
BELLMAN_FORD_T returns false if there is a negative cycle in G that is reachable from s and returns true otherwise. The algorithm ([9]) has running time O(min(D, n)m) where D is the maximal number of edges in any shortest path.
The algorithm is never significantly slower than BELLMAN_FORD_B and frequently much faster.

bool ALL_PAIRS_SHORTEST_PATHS_T(graph& G, edge_array<NT> c, node_matrix<NT>& DIST)

returns true if G has no negative cycle and returns false otherwise. In the latter case all values returned in DIST are unspecified. In the former case the following holds for all v and w: if $\mu$ (v, w) < $\infty$ then DIST(v, w) = $\mu$ (v, w) and if $\mu$ (v, w) = $\infty$ then the value of DIST(v,w) is arbitrary. The procedure runs in time O(nm + n²log n).

rational MINIMUM_RATIO_CYCLE(graph& G, edge_array<int> c, edge_array<int> p, list<edge>& C_star)

Returns a minimum cost to profit ratio cycle C_star and the ratio of the cycle. For a cycle C let c(C) be the sum of the c-values of the edges on the cycle and let p(C) be the sum of the p-values of the edges on the cycle. The cost to profit ratio of the cycle is the quotient c(C)/p(C). The cycle C_start realizes the minimum ratio for any cycle C. The procedure runs in time O(nmlog(n*C*P)) where C and P are the maximum cost and profit of any edge, respectively. The program returns zero if there is no cycle in G.
Precondition There are no cycles of cost zero or less with respect to either c or p.

Next: Maximum Flow ( max_flow Up: Graph Algorithms Previous: Basic Graph Algorithms ( Contents Index

LEDA research project
2000-02-09

bool	SHORTEST_PATH_T(graph G, node s, edge_array<NT> c, node_array<NT>& dist, node_array<edge>& pred)
		SHORTEST_PATH solves the single source shortest path problem in the graph G(V, E) with respect to the source node s and the cost-function given by the edge_array c. The procedure returns false if there is a negative cycle in G that is reachable from s and returns true otherwise. It runs in linear time on acyclic graphs, in time O(m + nlog n) if all edge costs are non-negative, and runs in time O(min(D, n)m) otherwise. Here D is the maximal number of edges on any shortest path.
node_array<int>	CHECK_SP_T(graph G, node s, edge_array<NT> c, node_array<NT> dist, node_array<edge> pred)
		checks whether the pair (dist, pred) is a correct solution to the shortest path problem (G, s, c) and returns a node_array<int> label with label[v] < 0 if v has distance - $\infty$ (-2 for nodes lying on a negative cycle and -1 for a node reachable from a negative cycle), label[v] = 0 if v has finite distance, and label[v] > 0 if v has distance + $\infty$ . The program aborts if the check fails. The algorithm takes linear time.
void	ACYCLIC_SHORTEST_PATH_T(graph G, node s, edge_array<NT> c, node_array<NT>& dist, node_array<edge>& pred)
		solves the single source shortest path problem with respect to source s. The algorithm takes linear time. Precondition G must be acyclic.
void	DIJKSTRA_T(graph G, node s, edge_array<NT> cost, node_array<NT>& dist, node_array<edge>& pred)
		solves the shortest path problem in a graph with non-negative edges weights. Precondition The costs of all edges are non-negative.
void	DIJKSTRA_T(graph G, node s, edge_array<NT> cost, node_array<NT>& dist)
		as above, but pred is not computed.
NT	DIJKSTRA_T(graph G, node s, node t, edge_array<NT> c, node_array<edge>& pred)
		computes a shortest path from s to t and returns its lenght. The cost of all edges must be non-negative. The return value is unspecified if there is no path from s to t. The array pred records a shortest path from s to t in reverse order, i.e., pred[t] is the last edge on the path. If there is no path from s to t or if s = t then pred[t] = nil. The worst case running time is O(m + nlog n), but frequently much better.
bool	BELLMAN_FORD_B_T(graph G, node s, edge_array<NT> c, node_array<NT>& dist, node_array<edge>& pred)
		BELLMAN_FORD_B solves the single source shortest path problem in the graph G(V, E) with respect to the source node s and the cost-function given by the edge_array c. BELLMAN_FORD_B returns false if there is a negative cycle in G that is reachable from s and returns true otherwise. The algorithm ([9]) has running time O(min(D, n)m) where D is the maximal number of edges on any shortest path. The algorithm is only included for pedagogical purposes.
void	BF_GEN(GRAPH<int,int>& G, int n, int m, bool non_negative = true)
		generates a graph with at most n nodes and at most m edges. The edge costs are stored as edge data. The running time of BELLMAN_FORD_B on this graph is $\Omega$ (nm). The edge weights are non-negative if non_negative is true and are arbitrary otherwise. Precondition m > = 2n and m < = n²/2.
bool	BELLMAN_FORD_T(graph G, node s, edge_array<NT> c, node_array<NT>& dist, node_array<edge>& pred)
		BELLMAN_FORD_T solves the single source shortest path problem in the graph G(V, E) with respect to the source node s and the cost-function given by the edge_array c. BELLMAN_FORD_T returns false if there is a negative cycle in G that is reachable from s and returns true otherwise. The algorithm ([9]) has running time O(min(D, n)m) where D is the maximal number of edges in any shortest path. The algorithm is never significantly slower than BELLMAN_FORD_B and frequently much faster.
bool	ALL_PAIRS_SHORTEST_PATHS_T(graph& G, edge_array<NT> c, node_matrix<NT>& DIST)
		returns true if G has no negative cycle and returns false otherwise. In the latter case all values returned in DIST are unspecified. In the former case the following holds for all v and w: if $\mu$ (v, w) < $\infty$ then DIST(v, w) = $\mu$ (v, w) and if $\mu$ (v, w) = $\infty$ then the value of DIST(v,w) is arbitrary. The procedure runs in time O(nm + n²log n).
rational	MINIMUM_RATIO_CYCLE(graph& G, edge_array<int> c, edge_array<int> p, list<edge>& C_star)
		Returns a minimum cost to profit ratio cycle C_star and the ratio of the cycle. For a cycle C let c(C) be the sum of the c-values of the edges on the cycle and let p(C) be the sum of the p-values of the edges on the cycle. The cost to profit ratio of the cycle is the quotient c(C)/p(C). The cycle C_start realizes the minimum ratio for any cycle C. The procedure runs in time O(nmlog(nCP)) where C and P are the maximum cost and profit of any edge, respectively. The program returns zero if there is no cycle in G. Precondition There are no cycles of cost zero or less with respect to either c or p.