Sind Sie verunsichert, den kürzesten Weg von Ihrem Standort zum Ziel zu finden? Dann sollten Sie über diesen Algorithmus Bescheid wissen.
- Der Floyd-Warshall-Algorithmus wird verwendet, um die kürzesten Wege zwischen allen Paaren von Knotenpunkten in einem Graphen zu finden, wobei jede Kante im Graphen ein positives oder negatives Gewicht hat.
- Der größte Vorteil dieses Algorithmus ist, dass alle kürzesten Wege zwischen zwei beliebigen Knoten in O(V3) berechnet werden können, wobei V die Anzahl der Knoten in einem Graphen ist.
- Der Floyd-Warshall-Algorithmus wird auch als Floyd-Algorithmus, Roy-Floyd-Algorithmus, Roy-Warshall-Algorithmus oder WFI-Algorithmus bezeichnet.
- Dieser Algorithmus folgt dem Ansatz der dynamischen Programmierung, um die kürzesten Wege zu finden.
Algorithmus
Für einen Graphen mit N Scheitelpunkten:
Schritt 1: Initialisiere die kürzesten Pfade zwischen 2 beliebigen Scheitelpunkten mit Unendlich.
Schritt 2: Finde alle paarweisen kürzesten Pfade, die 0 Zwischenscheitelpunkte verwenden, dann finde die kürzesten Pfade, die 1 Zwischenscheitelpunkt verwenden und so weiter… bis alle N Scheitelpunkte als Zwischenknoten verwendet werden.
Schritt 3: Minimiere die kürzesten Pfade zwischen 2 beliebigen Paaren in der vorherigen Operation.
Schritt 4: Für 2 beliebige Scheitelpunkte (i,j) sollte man eigentlich die Entfernungen zwischen diesem Paar minimieren, indem man die ersten K Knoten verwendet, so dass der kürzeste Pfad sein wird: min(dist+dist,dist).
dist stellt den kürzesten Pfad dar, der nur die ersten K Scheitelpunkte verwendet, dist stellt den kürzesten Pfad zwischen dem Paar k,j dar. Da der kürzeste Weg eine Verkettung des kürzesten Weges von i nach k und dann von k nach j ist.
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
dist = min( dist, dist + dist );
}
}
}
Beispiel
Lassen Sie den gegebenen Graphen sein:
Folgen Sie den folgenden Schritten, um den kürzesten Weg zwischen allen Paaren von Scheitelpunkten zu finden.
- Erstelle eine Matrix
A0der Dimensionn*n, wobei n die Anzahl der Scheitelpunkte ist. Die Zeile und die Spalte werden mit i bzw. j indiziert. i und j sind die Scheitelpunkte des Graphen.
Jede Zelle A wird mit der Entfernung vom ithScheitelpunkt zum jthScheitelpunkt gefüllt. Wenn es keinen Weg vom ith Scheitelpunkt zum jth Scheitelpunkt gibt, wird die Zelle als unendlich belassen.
2. Erstelle nun eine Matrix A1 mit der Matrix A0. Die Elemente in der ersten Spalte und der ersten Zeile werden so belassen, wie sie sind. Die restlichen Zellen werden folgendermaßen gefüllt.
Lassen Sie k den einfrierenden Knoten im kürzesten Weg von der Quelle zum Ziel sein. In diesem Schritt ist k der erste Vertex.A wird mit (A + A) if (A > A + A) gefüllt.
Das heißt, wenn die direkte Entfernung von der Quelle zum Ziel größer ist als der Weg durch den Vertex k, dann wird die Zelle mit A + A gefüllt.
In diesem Schritt ist k der Vertex 1. Wir berechnen die Entfernung vom Quell-Eckpunkt zum Ziel-Eckpunkt durch diesen Eckpunkt k.
Zum Beispiel: Für A1 ist der direkte Abstand von Scheitelpunkt 2 zu 4 gleich 4 und die Summe der Abstände von Scheitelpunkt 2 zu 4 durch Scheitelpunkt (d. h. von Scheitelpunkt 2 zu 1 und von Scheitelpunkt 1 zu 4) ist 7. Da 4 < 7, wird A0 mit 4 gefüllt.
3. Auf ähnliche Weise wird A2 mit A3 erstellt. Die Elemente in der zweiten Spalte und der zweiten Zeile werden so belassen, wie sie sind.
In diesem Schritt ist k der zweite Scheitelpunkt (d. h. Scheitelpunkt 2). Die übrigen Schritte sind die gleichen wie in Schritt 2.
4. Auf ähnliche Weise werden auch A3 und A4 erstellt.
A4 ergibt den kürzesten Weg zwischen jedem Paar von Scheitelpunkten.
Wählen Sie den kürzesten Weg aus, dann verwenden Sie den folgenden Code, um ihn zu finden. Gib aber die richtigen Abstände ein.
Zeitkomplexität
Es gibt drei Schleifen. Jede Schleife hat konstante Komplexitäten. Die Zeitkomplexität des Floyd-Warshall-Algorithmus ist also O(n3).
Raumkomplexität
Die Raumkomplexität des Floyd-Warshall-Algorithmus ist O(n2).