### 5.3.3. Algorithms for shortest paths

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.

Filename: ShortestPath.C
LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!
```#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;
}

// 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`.

#### Running times and further information

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).