Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


32. Gerichtete Graphen



Alle kürzesten Pfade

Die transitive Hülle eines ungewichteten Graphen (gerichtet oder nicht) beantwortet die Frage »Existiert ein Pfad von x nach y?« für alle Paare x, y von Knoten. Für gewichtete Graphen (gerichtet oder nicht) ist es manchmal wünschenswert, eine Tabelle anzugeben, die es gestattet, den kürzesten Pfad von x nach y für alle Paare von Knoten zu finden. Dies ist das Problem des kürzesten Pfades für alle Paare. Zum Beispiel möchten wir für den in Abbildung 32.5 dargestellten gewichteten Graph allein durch Zugriff auf diese Tabelle erfahren, daß der kürzeste Pfad von M nach K die Länge 8 hat, der kürzeste Pfad von J nach F die Länge 12 usw.

Abbildung 32.5
Abbildung 32.5 Ein gewichteter gerichteter Graph.

Wie oben findet der Algorithmus des kürzesten Pfades aus dem vorangegangenen Kapitel den kürzesten Pfad vom Anfangsknoten zu jedem anderen Knoten, so daß wir nur diese Prozedur V mal anwenden müssen, beginnend in jedem Knoten. Dies ergibt einen Algorithmus, der in O((E + V)V log V) Schritten abläuft. Doch es ist auch möglich, ein Verfahren anzuwenden, das mit dem Verfahren von Warshall vergleichbar ist und gewöhnlich R. W. Floyd zugeschrieben wird:

    for y:=1 to V do
      for x:=1 to V do
        if a[x,y]>0 then
          for j:=1 to V do
            if a[y,j]>0 then
              if (a[x,j]=0) or (a[x,y]+a[y,j]<a[x,j])
                then a[x,j]:=a[x,y]+a[y,j];

Die Struktur des Algorithmus ist genau die gleiche wie beim Verfahren von Warshall. Anstelle der Verwendung von OR zur Verfolgung der Pfade führen wir für jede Kante eine kleine Berechnung aus, um zu bestimmen, ob sie Teil eines neuen kürzesten Pfades ist: »Der kürzeste Weg von Knoten x nach Knoten j unter ausschließlicher Benutzung von Knoten mit Indizes, die kleiner als y + 1 sind, ist entweder der kürzeste Weg von Knoten x nach Knoten j unter ausschließlicher Benutzung von Knoten mit Indizes, die kleiner als y sind, oder, wenn er kürzer ist, der kürzeste Weg von x nach y plus dem Abstand zwischen y und j.« Wie gewöhnlich entspricht ein Eintrag 0 in der Matrix dem Fehlen der angegebenen Kante; das Programm könnte etwas vereinfacht werden (indem alle Vergleiche auf 0 entfallen), wenn ein als Marke dienender Wert verwendet wird, der einer Kante mit unendlich großem Gewicht entspricht.

Eigenschaft 32.3 Der Algorithmus von Floyd ermöglicht die Lösung des Problems des kürzesten Pfades für alle Paare in O(V3) Schritten.

Dies folgt aus den gleichen Überlegungen wie im Falle der Eigenschaft 32.2. w.z.b.w.

Abbildung 32.6
Abbildung 32.6 Anfangsetappen
des Algorithmus von Floyd.

Die Abbildungen 32.6 und 32.7 zeigen das Verhalten des Algorithmus von Floyd ausführlicher anhand unseres Beispiels, das zum Zwecke des Vergleichs genauso wie die Abbildungen 32.3 und 32.4 angeordnet wurde. Die Nulleinträge in den verschiedenen Matrizen, die dem Fehlen eines Pfades zwischen den beiden Knoten mit den betreffenden Indizes entsprechen, sind für beide Algorithmen identisch. Die von null verschiedenen Einträge in den Matrizen für den Algorithmus von Warshall bezeichnen die Existenz eines Pfades zwischen den beiden Knoten; beim Algorithmus von Floyd geben sie die Länge des kürzesten solchen Pfades an, der schon entdeckt worden ist. Der aktuell kürzeste Pfad kann auch berechnet werden, indem eine Matrixvariante unseres Feldes dad aus den vorangegangenen Kapiteln benutzt wird: Man setze den Eintrag in Zeile x und Spalte j auf den Namen des letzten Knotens im kürzesten Pfad von x nach j (Knoten y in der inneren Schleife des obigen Programms).

Abbildung 32.7
Abbildung 32.7 Letzte Etappen des Algorithmus von Floyd.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]