Was ist das Prinzip des Floyd-Algorithmus?

Das Prinzip des Floyd-Algorithmus ist ein Algorithmus, der die Idee der dynamischen Programmierung verwendet, um den kürzesten Weg zwischen mehreren Quellpunkten in einem bestimmten gewichteten Diagramm zu finden. Er ähnelt dem Dijkstra-Algorithmus, der in gewichteten Diagrammen zu finden ist positive oder negative Kantengewichte.

Floyd算法, auch als Interpolationspunktmethode bekannt, ist ein Algorithmus, der die Idee der dynamischen Programmierung nutzt, um den kürzesten Weg zwischen mehreren Quellpunkten in einem bestimmten gewichteten Diagramm zu finden, ähnlich dem Dijkstra-Algorithmus. Der Algorithmus ist nach Robert Floyd benannt, einem der Gründer, Gewinner des Turing Award 1978 und Professor für Informatik an der Stanford University

In der Informatik ist der Floyd-Warshall-Algorithmus eine Methode, die positive oder negative Kanten hat Algorithmus zum Finden des kürzesten Pfades in einem gewichteten Diagramm mit Gewichten (jedoch ohne negative Perioden). Eine einzelne Ausführung des Algorithmus ermittelt die Länge (gewichtet) des kürzesten Pfades zwischen allen Scheitelpunktpaaren. Obwohl keine Details zum Pfad selbst zurückgegeben werden, kann der Pfad mit einfachen Änderungen am Algorithmus rekonstruiert werden. Versionen dieses Algorithmus können auch verwendet werden, um den transitiven Abschluss einer Beziehung R oder (im Zusammenhang mit dem Schulze-Voting-System) den breitesten Pfad zwischen allen Scheitelpunktpaaren in einem gewichteten Graphen zu finden.

Der Floyd-Warshall-Algorithmus ist ein Beispiel für dynamische Programmierung und wurde 1962 in seiner derzeit akzeptierten Form von Robert Floyd veröffentlicht. Es handelt sich jedoch im Wesentlichen um denselben Algorithmus zum Finden transitiver Abschlüsse von Graphen, der zuvor von Bernard Roy im Jahr 1959 und Stephen Warshall im Jahr 1962 veröffentlicht wurde, und ist eng mit Kleenes Algorithmus von 1956 zum Konvertieren deterministischer endlicher Automaten in reguläre Ausdrücke verwandt. Die moderne Formulierung des Algorithmus als drei verschachtelte for-Schleifen wurde erstmals 1962 von Peter Ingerman beschrieben.

Dieser Algorithmus ist auch als Floyd-Algorithmus, Roy-Warshall-Algorithmus, Roy-Floyd-Algorithmus oder WFI-Algorithmus bekannt.

Kernideen-Editor

1. Finden Sie die kürzeste Pfadmatrix zwischen jeweils zwei Punkten eines Diagramms anhand seiner Gewichtsmatrix.

Führen Sie ausgehend von der gewichteten Adjazenzmatrix A = [a (i, j)] n × n des Diagramms rekursiv n Aktualisierungen durch, dh ausgehend von der Matrix D (0) = A gemäß einer Formel die Matrix D( 1); und verwenden Sie dieselbe Formel, um D(2) aus D(1); zu konstruieren....; Verwenden Sie schließlich dieselbe Formel, um die Matrix D(n) aus D(n-1) zu konstruieren. Die Elemente in Zeile i und Spalte j der Matrix D(n) sind die kürzeste Pfadlänge vom Scheitelpunkt i zum Scheitelpunkt d(n) und werden gleichzeitig als Abstandsmatrix des Diagramms bezeichnet Außerdem wird der kürzeste Weg eingeführt, um den Abstand zwischen zwei Punkten aufzuzeichnen.

Verwenden Sie die Entspannungstechnologie (Entspannungsoperation), um alle anderen Punkte zwischen i und j zu entspannen. Die Zeitkomplexität ist also O(n^3);

2. Die Zustandsübergangsgleichung lautet wie folgt: map[i,j]:=min{map[i,k]+map [k, j], map[i,j]};

map[i,j] stellt die kürzeste Entfernung von i nach j dar, K ist der Haltepunkt für vollständiges i,j und der Anfangswert von map[n, n] sollte 0 sein, oder tun Sie es entsprechend der Bedeutung der Frage. Wenn diese Straße nicht zugänglich ist, muss natürlich eine spezielle Verarbeitung durchgeführt werden, z. B. gibt es keine Karte [i, k] Straße.

Algorithmus-Prozesseditor

1, beginnen Sie mit einem beliebigen einseitigen Pfad. Der Abstand zwischen allen beiden Punkten ist das Gewicht der Kante. Wenn es keine Kante gibt, die die beiden Punkte verbindet, ist das Gewicht unendlich.

2. Überprüfen Sie für jedes Scheitelpunktpaar u und v, ob es einen Scheitelpunkt w gibt, sodass der Weg von u nach w nach v kürzer ist als der bekannte Weg. Wenn ja, aktualisieren Sie es. Stellen Sie den Graphen als Adjazenzmatrix G dar. Wenn es eine Straße gibt, die von Vi nach Vj erreichbar ist, dann ist G[i][j]=d, d stellt die Länge der Straße dar; andernfalls ist G[i][j]= Unendlichkeit. Definieren Sie eine Matrix D, um die Informationen des eingefügten Punkts D[i][j] aufzuzeichnen, der den Punkt darstellt, der von Vi an Vj übergeben werden muss. Fügen Sie jeden Scheitelpunkt in das Diagramm ein und vergleichen Sie den Abstand nach dem Einfügen mit dem ursprünglichen Abstand, G[i][j] = min( G[i][j], G[i][k]+G[k][j ] ), wenn der Wert von G[i][j] kleiner wird, dann ist D[i][j]=k. G enthält die Informationen über die kürzeste Straße zwischen zwei Punkten, während D die Informationen über den kürzesten Weg enthält.

Zum Beispiel wollen wir den Weg von V5 nach V1 finden. Laut D bedeutet D(5,1)=3, dass der Pfad von V5 nach V1 durch V3 verläuft: {V5,V3,V1}. Wenn D(5,3)=3, bedeutet dies, dass V5 und V3 sind direkt verbunden. Wenn D (3,1)=1, bedeutet dies, dass V3 und V1 direkt verbunden sind.

Zeitkomplexität und Raumkomplexitätsbearbeitung

Zeitkomplexität: O(n^3);

Raumkomplexität: O(n^2)

Vor- und Nachteile der Analyse und Bearbeitung

Floyd-Algorithmus ist anwendbar Bei APSP (All Pairs Shortest Paths, kürzester Pfad aus mehreren Quellen) handelt es sich um einen dynamischen Programmieralgorithmus, der die beste Wirkung auf dichte Diagramme hat und dessen Kantengewichte positiv oder negativ sein können. Aufgrund der kompakten Dreifachschleifenstruktur ist die Effizienz höher als die Ausführungszeit des Dijkstra-Algorithmus und höher als die Ausführungszeit des SPFA-Algorithmus.

Vorteile: Leicht verständlich, kann den kürzesten Abstand zwischen zwei beliebigen Knoten berechnen und der Code ist einfach zu schreiben. Nachteile: Die zeitliche Komplexität ist relativ hoch und für die Berechnung großer Datenmengen nicht geeignet.

Das obige ist der detaillierte Inhalt vonWas ist das Prinzip des Floyd-Algorithmus?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!