Schon in Abschnitt “Ein Anwendungsbeispiel: Breitensuche in einem Graphen” haben wir uns mit kürzesten Wegen in Graphen beschäftigt. Dort haben wir festgestellt, dass in einem Graphen, in dem die Kanten keine Abstandsinformation tragen oder alle Abstände zwischen den Knoten gleich sind, die kürzesten Wege von einem Startknoten aus zu allen anderen Knoten durch Breitensuche berechnet werden können.

Häufig kommt es aber vor, dass die Knoten unterschiedliche Abstände voneinander aufweisen, wie etwa in Abbildung 5.20; wir können uns die Knoten daraus z. B. als Bahnhöfe vorstellen und die Kanten als Bahnstrecken, die mit der Länge dieser Strecke beschriftet sind. Wiederum stellt sich dann in natürlicher Weise die Frage, welches ein kürzester Pfad (Weg) von einem Startknoten s zu einem anderen Knoten t ist. Als Reisende wollen wir selbstverständlich so wenig Kilometer wie möglich fahren, denn bei der Deutschen Bahn bezahlt man pro gefahrenem Kilometer!

Abbildung 5.20. Ein Abstands-Graph und kürzeste Wege darin

Die Knoten sind als Bahnhöfe zu interpretieren, die Kanten als Bahnstrecken dazwischen. Die Beschriftung einer Kante entspricht der Länge der Strecke von Bahnhof A zu Bahnhof B. Der Graph ist gerichtet. I. Allg. existiert zu jeder Kante auch eine Rückwärtskante, weil man im Normalfall immer auch von B nach A zurückfahren kann. Diese Strecke muss aber nicht gleich lang sein und sie muss nicht immer existieren.

Die kürzesten Wege vom Knoten A aus sind als dicke Kanten gezeichnet. Erreichbare Knoten haben eine dicke Umrandung.

Die Länge eines Pfades ist hier die Summe der Abstandsinformationen der Kanten des Pfades. Ein kürzester Pfad von s nach t ist ein Pfad von s nach t, dessen Länge in Bezug auf alle anderen Pfade von nach nach t minimal ist. (Oft werden kürzeste Pfade auch als „kürzeste Wege“ bezeichnet.) Diese Länge wird als Distanz von s nach t bezeichnet.

Existiert ein solcher kürzester Weg zwischen zwei Knoten s und t immer? Zunächst einmal muss natürlich t von s aus erreichbar sein. Ist er dies nicht, so gibt es überhaupt keinen Weg, also auch kürzesten, und die Distanz von s nach t wird als minus unendlich festgelegt. Problematisch sind auch negative Zyklen, d. h., Zyklen, deren Kantensumme negativ ist. (Es gibt durchaus Abstands-Graphen, die Kanten mit negativer Abstandsinformation enthalten.) Da ein solcher Zyklus in einem Pfad beliebig oft durchlaufen werden darf, kann die Länge des Pfades immer kleiner gemacht werden, kleiner als jede negative Zahl; daher wird auch in diesem Fall die Distanz als minus unendlich angesehen. Noch schlimmer: Alle Distanzen in einer starken Zusammenhangskomponente, die einen negativen Zyklus enthält, sind -∞.

Zur Lösung solcher Kürzeste-Wege-Probleme (shortest path problems) bietet LEDA einige Funktionen an, die alle in der Header-Datei shortest_path.h deklariert sind.

Als Beispiel daraus zeigen wir die Verwendung der Funktion SHORTEST_PATH():

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

Diese Funktion erwartet in einem auf dem gerichteten Graphen G gültigen Kanten-Array cost die Abstände der einzelnen Knoten zueinander und berechnet für jeden Knoten w in G die Distanz vom Starknoten s nach w; diese Distanz legt sie im Knoten-Array dist ab. Die kürzesten Wege von s zu jedem anderen Knoten w legt sie im Knoten-Array pred ab: Jedem Knoten wird die zu ihm inzidente Kante auf einem kürzesten Weg von s aus mitgeteilt; durch Zurücklaufen entlang dieser Kanten kann der kürzeste Weg von s nach w konstruiert werden. (Der Wert dieser Kante ist nil, wenn w nicht erreichbar ist.) Die Funktion liefert false zurück, wenn es einen negativen Zyklus gibt, der von s aus erreichbar ist. In diesem Fall sind alle Distanzwerte als minus unendlich anzusehen; es hat dann wenig Sinn, von „kürzesten Wegen von s aus“ zu reden.

Das folgende Programm lässt den Benutzer einen (gerichteten) Graphen editieren, wobei er die Data-Labels der Kanten mit Abstandsinformationen beschriften muss. Danach kann er einen Startknoten s mit der Maus selektieren. Von diesem ausgehend berechnet dann SHORTEST_PATH() die kürzesten Wege zu den anderen Knoten und gibt diese aus. Abbildung 5.20 wurde damit erzeugt.

#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;
    }
  }
}

Das Programm gibt folgende kürzesten Wege aus, wenn wir in Abbildung 5.20 zuerst mit der mittleren Maustaste den Knoten A als Startknoten auswählen und dann auf done drücken:

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

Um im Edit-and-Run-Zyklus herauszufinden, welchen Knoten der Benutzer selektiert hat, verwenden wir die Methode get_selected_nodes() der Klasse GraphWin, die eine Liste der augenblicklich selektierten Knoten zurückgibt. Ist keiner oder mehr als ein Knoten selektiert, geht das Programm sofort in den nächsten Editiervorgang über.

Nachdem SHORTEST_PATH() die kürzesten Wege berechnet hat, benutzen wir die Kanten im Knoten-Array pred, um von jedem Knoten w entlang eines kürzesten Pfades zu s zurückzulaufen. Wir sammeln die dabei traversierten Knoten in einer node_list auf, die wir in umgekehrter Reihenfolge der Aufnahme wieder ausgeben. Dies ist zudem ein sinnvolles Beispiel für die Verwendung der speziellen Hilfsdatenstruktur node_list.