*Learning objectives*

Algorithms from `shortest_path.h` |

Shortest paths in distance graphs |

Already in Section “A working example: Breadth first search in a graph” we
concerned ourselves with shortest paths in graphs. There we found
that in a graph in which the edges carry no distance information
or in which all distances are equal, the shortest paths from a
start node to all other nodes can be computed by
*breadth first search*.

Often, however, it happens that the nodes exhibit different distances from one another, like in Figure 5.20, for instance; we may imagine these nodes as railroad stations, for example, and the edges as railroad tracks that are labeled with the length of this track. Again the question arises, of course, which path (track) is a shortest one from a start node s to a target node t. As travelers we want to travel as few kilometers as possible, of course. On a journey with the Deutsche Bahn, we pay per kilometer traveled!

The *length of a path* is the sum of
the distance values of the edges of this path. A
*shortest path from s to t* is a path from s
to t whose length is minimal with respect to all other paths from
s to t. This length is called the *distance of t from s*.

Does such a shortest path from a node s to a node t always
exist? First of all, t has to be reachable from s, of course. If it
is not, there is no path at all, and the distance from s to t is
defined as minus infinity. *Negative cycles* are
problematic, too. These are cycles whose edge sum is
negative. (Indeed, there are distance graphs that contain edges
with negative distance information.) As such a cycle may be
traversed arbitrarily many times in a path, the length of the path
can be decreased more and more, to a value smaller than any
negative number; hence also in this case, the distance is
considered to be minus infinity. Even worse: All distances in a
strongly connected component that contains a negative cycle are
-∞.

LEDA offers some functions to solve such *shortest
path problems*; they all
are declared in the header file * shortest_path.h*.

As an example of these, we show the usage of the function * SHORTEST_PATH()*:

bool SHORTEST_PATH(graph& G, node s, edge_array<int>& cost, node_array<int>& dist, node_array<edge>& pred);

This function expects the distances of the individual nodes from one
another in an edge array `cost`

that is valid on the
directed graph `G`

. For each node w in
`G`

, it computes the distance of w from the start
node `s`

; it records this distance in the node array
`dist`

. It records the shortest paths from
`s`

to each other node w in the node array
`pred`

: Each node is told the edge incident to it on
a shortest path from s; the shortest path from `s`

to
w can be constructed by walking back along the edges in
`pred`

. (This edge value is `nil`

if
w is not reachable.) The function returns `false`

if
there is a negative cycle reachable from `s`

. in this
case, all distance values are considered to be -∞; then it
does not make much sense to speak of “shortest paths from
`s`

”.

The following program allows the user to edit an
undirected graph. He must fill the data labels of the edges
with distance information. Thereafter, he may select a start
node s with the mouse. Starting from this node,
`SHORTEST_PATH()`

then computes the shortest
paths to the other nodes and outputs them. Figure 5.20 has been created with this
program.

#include <LEDA/shortest_path.h> #include <LEDA/graph.h> #include <LEDA/graphwin.h> #include <LEDA/node_list.h> #include <LEDA/list.h> #include <LEDA/color.h> #include <iostream> using leda::GRAPH; using leda::GraphWin; using leda::window; using leda::color; using leda::node; using leda::edge; using leda::node_array; using leda::edge_array; using leda::node_list; using leda::list; using leda::string; using std::cout; using std::endl; int main() { GRAPH<string,int> G; GraphWin gw(G, 500, 700, "Shortest Path"); gw.set_edge_label_type(leda::data_label); gw.set_node_label_type(leda::data_label); gw.set_node_border_width(2); gw.set_flush(false); gw.display(window::center,window::center); while(gw.edit()) { // get start node s: get the one selected node of GraphWin node s; list<node> L = gw.get_selected_nodes(); if(L.size() != 1) { gw.message("No start node or more than one selected! Click <done>."); gw.wait(); gw.del_message(); continue; } else s = L.head(); // setup cost information: use information associated to GRAPH<,> edge_array<int> cost(G); edge e; forall_edges(e,G) cost[e] = G.inf(e); // setup node arrays for distance and predecessors node_array<int> dist(G); node_array<edge> pred(G); // compute shortest paths from s if(SHORTEST_PATH(G, s, cost, dist, pred)) { // shortest paths may have changed: reset attribute values gw.set_edge_color(leda::black); gw.set_edge_width(1); gw.set_node_border_color(leda::black); gw.set_node_border_width(1); cout << "The distances of the cities to "; cout << G.inf(s) << " are:" << endl; node v; forall_nodes(v, G) { if(v == s) { // distance is trivially 0 gw.set_border_color(v, leda::green); gw.set_border_width(v, 4); continue; } cout << G.inf(v) << ": "; if(pred[v] == nil) { // v not reachable cout << G.inf(v) << " not reachable (infinite distance)."; cout << endl; continue; } cout << dist[v] << " km"; // collect nodes on path back to s node_list path; node w = v; w = G.opposite(w, pred[w]); while(w != s) { path.push(w); // reverse ordering w = G.opposite(w, pred[w]); } // if there are any, output them in reverse order if(!path.empty()) { cout << " via "; node x; forall(x, path) cout << G.inf(x) << " "; } cout << endl; // show edge as edge of a shortest path gw.set_color(pred[v], leda::red); gw.set_width(pred[v], 4); gw.set_border_color(v, leda::red); gw.set_border_width(v, 4); } gw.redraw(); } else { // SHORTEST_PATH returned false cout << "This graph contains a negative cycle "; cout << "reachable from s." << endl; } } }

If, in Figure 5.20, we first choose the node A as the start node and then press , the program outputs the following:

The distances of the cities to A are: C: 5 km via D B B: 4 km via D D: 2 km G: 7 km via D F M: 7 km via D F J L: 8 km via D F G H: 6 km via D B I: 8 km via D B H F: 4 km via D E: E not reachable (infinite distance). O: 9 km via D F J M K: 9 km via D F G L P: 10 km via D F J M O J: 6 km via D F N: 9 km via D F J

In the edit-and-run cycle, to find out which node has been
selected by the user, we use the method
`get_selected_nodes()`

of class
`GraphWin`

, which returns a list of the nodes
currently selected. If zero or more than one nodes are selected,
the program immediately goes into the next edit operation.

After `SHORTEST_PATH()`

has computed the
shortest paths, we use the edges in the node array
`pred`

to walk back to `s`

from each node `w`

along a
shortest path. Doing this, we collect the edges that we traverse
in a `node_list`

, which we output in reverse
order of insertion. This is in addition a reasonable example
for the use of the of the special auxiliary data structure `node_list`

.

On acyclic graphs, the function
`SHORTEST_PATH()`

has a running time of
O(n+m). On cyclic graphs, it takes time O(m+n·log(n)) if
all distance values of the edges are non-negative. In contrast,
if there are negative distances, it takes time
O(m·min(D,n)) with D being the maximal number of edges on
a shortest path in the graph. (This number is +∞ if there
are negative cycles, but please note the minimum function in the
expression!)

There are further functions for computing shortest paths
declared in `shortest_path.h`

. For example,
there is `ALL_PAIRS_SHORTEST_PATHS()`

, which
computes the length of a shortest path from v to w for all pairs
of nodes (v,w).

More information about these functions can be found on the corresponding manual page.