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!

Figure 5.20. A distance graph and shortest paths therein

The nodes may be imagined as railroad stations, the edges as connecting tracks. The labeling of an edge corresponds to the length of the track from station A to station B. The graph is directed. In general, there is also a reverse edge for every edge, because in the normal case, one can travel back from B to A, too. This track, however, does not have to have the same length, and it does not always have to exist.

The shortest paths starting from node A are drawn as thick edges. Reachable nodes have a thick border.

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 done, 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.