Was sind die günstigsten Wege zwischen Knotenpaaren?

Kürzeste Pfade zwischen allen Paaren von Knoten

Wenn man die Distanzen zwischen verschiedenen Orten berücksichtigt, zum Beispiel im Bereich Logistik, kommen die Aufgaben über die kürzeste Wege oft vor. In diesen Situationen können die Orte als die Knoten und die Kanten als Wege im Graph dargestellt werden.

Bei der Lösung vieler Aufgaben muss man die kürzeste Wege zwischen allen Paaren von Knoten eines Graphen bestimmen und deren Längen berechnen. Der Floyd-Warshall Algorithmus, der dieses Problem löst, kann auf dem beliebigen Graph ausgeführt werden, wobei es wichtig ist, dass er keine negative Kreise enthält. Falls es negative Kreise im Graph gibt, dann können die genutzt werden um beliebig kleinen (negativen) Wege zwischen einigen Knoten zu konstruieren. In diesem Fall kann der Algorithmus keinen optimalen Wert erzeugen.

Hier wird der Floyd-Warshall-Algorithmus vorgestellt, der günstigste Wege zwischen allen Paaren von Knoten berechnet.

Kürzeste Wege

Als Beispiel könnte man das folgende Problem betrachten: es gibt 10 Städte, die miteinander durch verschiedenen Autobahnen verbunden sind. Die Aufgabe besteht darin, die minimale Distanzen zwischen allen Städten zu berechnen um die Transportkosten zu minimieren.

Gegeben ist ein Graph. Mit dem Algorithmus von Floyd-Warshall kann man kürzeste beziehungsweise günstigste Wege zwischen allen Paaren von Knoten berechnen, wenn der Graph keine negative Kreise enthält. Ein Kreis in der Graphentheorie ist ein Weg in einem Graphen, bei dem Start- und Endknoten gleich sind. Ein negativer Kreis heißt ein Kreis, wo die Summe der Kantenkosten weniger als 0 ist.

Dieses Problem kann mithilfe des Floyd-Warshall Algorithmus gelöst werden. Das gesamte Netz, das bei der Aufgabe gegeben ist, kann als ein Graph dargestellt werden. Die Knoten stehen nämlich für die Städte und die Kanten können die Autobahnen repräsentieren. Jede Kante bekommt eine Kost, die gleich der Entfernung zwichen Nachbarstädten in Metern oder Kilometern ist. Das Ziel ist die kürzesten Wege zwischen allen Städten zu berechnen.

Idee des Algorithmus

Der Pfad (a, d) wurde verbessert.

Das Prinzip des Floyd-Warshall-Algorithmus ist dynamische Programmierung. Das heißt, alle möglichen Pfade zwischen allen Paaren von Knoten werden schrittweise verglichen, wobei nur die besten Werte gespeichert werden.

Der Algorithmus geht von folgender Beobachtung aus: wenn der kürzeste Weg von u nach v durch w geht, dann sind die Teilpfade von u nach w und von w nach v auch minimal. Die Richtigkeit des Ergebnisses kann durch Induktion bewiesen werden. Der Floyd-Warshall Algorithmus funktioniert iterativ.

Sei G ein Graph, wo alle Knoten 1 bis N nummeriert sind. Beim Schritt k sei kürzesterWeg(i, j, k) eine Funktion, die den kürzesten Pfad von i nach j zurückgibt, wobei nur die Knoten aus der Menge {1, 2, ... k} als Zwischenpunkte dieses Weges sein können. Im nächsten Schritt muss der Algorithmus wieder die kürzeste Pfade zwischen allen i und j aus der Knotenmenge {1, ..., k + 1} finden.

Für alle solchen Knotenpaaren gilt, dass der kürzeste Weg entweder ein Weg mit Knoten nur aus der Menge {1, ..., k} oder ein Weg, der von i nach k + 1 und von k + 1 nach j geht, ist. Das bedeutet, beim Schritt (k + 1) kann der Weg von i nach j entweder gleich kürzesterWeg(i, j, k) bleiben oder zu kürzesterWeg(i, k + 1, k) + kürzesterWeg(k + 1, j, k) verbessert werden, je nachdem welche Länge kürzer ist. Das heißt, der Weg zwischen i und j kann gleich wie beim vorigen Schritt bleiben oder einen neuen Knoten k + 1 enthalten.

Darin besteht die Idee der dynamischen Programmierung. Bei jeder Iteration werden die aktuelle Pfadkosten zwischen allen Paaren von Knoten zugewiesen:

kürzesterWeg(i, j, k) = min(kürzesterWeg(i, j, k), kürzesterWeg(i, k + 1, k) + kürzesterWeg(k + 1, j, k))

Am Ende des Ablaufs von Floyd-Warshall darf jeder Pfad beliebigen Zwischenknoten enthalten, aber der Algorithmus speichert nur den günstigsten Wert für jedes Knotenpaar. Alle Werte sind optimal, weil der Algorithmus beim jeden Schritt den Wert ändert, falls die neue Kost niedriger ist.

Finden von günstigsten Wegen

Um die günstigste Wege zu finden, muss der Algorithmus eine Matrix speichern, die die aktuelle Kosten zwischen allen Paaren von Knoten enthält. Die Zeilen- und Spaltenindexe stellen die Knoten dar und die Werte in der Matrix stehen für die Distanzen zwischen den entsprechenden Knoten.

Angenommen der Graph ist gegeben durch seine Gewichtsmatrix W. Der Matrixeintrag W[i,j] ist das Gewicht der Kante von i nach j, falls eine solche Kante existiert. Falls es keine Kante von i nach j gibt ist W[i,j] unendlich.

Der Floyd-Warshall Algorithmus verwendet den Konzept der dynamischen Programmierung (siehe oben). Zunächst wird der Algorithmus initialisiert:

• Die Matrix D der kürzesten Distanzen wird mit den gleichen Längen wie die Gewichtsmatrix W initialisiert.
• Der Algorithmus führt die Hauptschleife mit k von 1 bis n aus. Bei jeder Iteration in dieser Schleife versucht der Algorithmus alle (i, j) Wege durch Wege (i, k) und (k, j) verbessern.
• Bei jeder Iteration werden die Distanzen zwischen allen Paaren von Knoten i, j betrachtet. Der Algorithmus prüft, ob (i, k) mit (k, j) kürzer als derzeitige (i, j) Länge ist.
• Falls ob die Distanz zwischen Knoten i, k und k, j kürzer als die aktuelle Distanz ist, dann wird die Distanz zwischen Knoten i und j aktualisiert.

Graphen mit negativen Kreisen

Ein negativer Kreis ist ein Kreis, dessen Kantengewichte eine negative Summe bilden. Wenn der Graph einen oder mehrere negative Kreise enthält, dann gibt es keinen kürzesten Weg zwischen Knoten, die den Teil des negativen Kreises bilden. Der Weg zwischen diesen Knoten ist beliebig klein (negativ). Damit der Floyd-Warshall Algorithmus richtiges Ergebnis erzeugt, muss es keine negative Kreise im Graphen geben.

Der Algorithmus kann genutzt werden um die negative Kreise im Graphen zu entdecken. Dafür muss der Algorithmus alle Paaren von Knoten (i, j) betrachten einschließlich die, wo i = j. Wenn irgendeine Kost (i, i) nach dem Ablauf des Algorithmus in der Distanzmatrix negativ ist, dann enthält der Graph mindestens einen negativen Kreis.

Im Beispiel auf dem Bild ist der Kreis (b, c, d) negativ. Das heißt, man kann unendlichmal durch diesen Kreis laufen und die Wege zwischen beliebigen Knoten aus diesem Kreis werden jeweils kürzer. Außerdem kann der Weg zwischen Knoten a und e im gegebenen Beispiel beliebig klein sein, weil der Pfad zwischen diesen Knoten den negativen Kreis enthalten kann.

Was nun?

Wie sieht der (Pseudo-)Code des Algorithmus aus?

Eingabe: Gewichteter, ungerichteter oder gerichteter Graph G=(V,E) mit Gewichtsfunktion w,
         wobei der Graph keine negative Kreise enthält.
Ausgabe: eine Matrix D, die die kürzesten Distanzen enthält.

BEGIN
  FOR ALL v ∈ V
    D[v][v] ← 0
  FOR ALL (u,v) ∈ E
    D[u][v] ← w(u,v)
  FOR k from 1 to |V|
    FOR i from 1 to |V|
      FOR j from 1 to |V|
        if D[i][j] > D[i][k] + D[k][j]
          D[i][j] ← D[i][k] + D[k][j]
        end if
END

Wie schnell ist der Algorithmus?

Berechnet der Algorithmus wirklich die kürzesten Wege?

Wo finde ich noch mehr Informationen zu Graphalgorithmen?

Ein letzter Hinweis zum Ziel und Inhalt dieser Seite und zu Zitationen