Algorithmus für den kürzesten Weg

Unter den Pfaden, die an einem Scheitelpunkt beginnen und entlang der Kanten des Diagramms zu einem anderen Scheitelpunkt führen, wird der Pfad mit der kleinsten Summe der Gewichte an jeder Kante als kürzester Pfad bezeichnet. Es gibt die folgenden Algorithmen zur Lösung des Kürzeste-Wege-Problems: Dijkstra-Algorithmus, Bellman-Ford-Algorithmus, Floyd-Algorithmus und SPFA-Algorithmus usw.

Definition

Das Kürzeste-Wege-Problem ist ein klassisches Algorithmusproblem in der Graphentheorieforschung, das darauf abzielt, Graphen zu finden ( Der kürzeste Weg zwischen zwei Knoten (bestehend aus Knoten und Pfaden). Die spezifische Form des Algorithmus umfasst:

(1) Das Problem, den kürzesten Weg vom Startpunkt aus zu bestimmen – das heißt, das Problem, den kürzesten Weg zu finden, wenn der Startknoten bekannt ist. Geeignet für die Verwendung des Dijkstra-Algorithmus. (Empfohlenes Lernen: PHP-Video-Tutorial)

(2) Das Problem, den kürzesten Weg zum Endpunkt zu bestimmen – Im Gegensatz zum Problem, den Startpunkt zu bestimmen, ist dieses Problem zu finden Frage nach dem kürzesten Weg, wenn der Endknoten bekannt ist. In einem ungerichteten Graphen entspricht dieses Problem vollständig dem Problem der Bestimmung des Startpunkts. In einem gerichteten Graphen entspricht dieses Problem dem Problem der Bestimmung des Startpunkts durch Umkehr der Richtungen aller Pfade.

(3) Das Problem besteht darin, den kürzesten Weg zwischen dem Startpunkt und dem Endpunkt zu bestimmen, dh bei gegebenem Startpunkt und Endpunkt den kürzesten Weg zwischen den beiden Knoten zu finden.

(4) Globales Problem des kürzesten Weges – Finden Sie alle kürzesten Wege im Diagramm. Geeignet für die Verwendung des Floyd-Warshall-Algorithmus.

Dijkstra

Finden Sie den kürzesten Weg mit einer einzigen Quelle und ohne negative Gewichtung. Die Aktualität ist gut und die Zeitkomplexität beträgt O(V*V+E). Wenn der Quellpunkt erreichbar ist, gilt O(V*lgV+E*lgV) =>O(E*lgV).
Wenn es sich um einen spärlichen Graphen handelt, ist zu diesem Zeitpunkt E=V*V/lgV, sodass die zeitliche Komplexität des Algorithmus O(V^2) sein kann. Wenn der Fibonacci-Heap als Prioritätswarteschlange verwendet wird, beträgt die Zeitkomplexität des Algorithmus O(V*lgV + E).

Floyd

Finden Sie den kürzesten Weg mit mehreren Quellen und ohne negative Gewichtskanten. Verwenden Sie eine Matrix, um das Diagramm aufzuzeichnen. Die Aktualität ist schlecht und die Zeitkomplexität beträgt O(V^3).
Der Floyd-Warshall-Algorithmus ist ein Algorithmus zur Lösung des kürzesten Pfads zwischen zwei beliebigen Punkten. Er kann das Problem des kürzesten Pfads eines gerichteten Graphen oder eines negativen Gewichts korrekt behandeln.

Bellman-Ford

Um den kürzesten Weg aus einer einzigen Quelle zu finden, können Sie bestimmen, ob es eine negative Gewichtsschleife gibt (wenn ja, dann gibt es keine). kürzester Weg),
Aktualität Besser, Zeitkomplexität O(VE).

Der Bellman-Ford-Algorithmus ist ein Algorithmus zur Lösung des Single-Source-Shortest-Path-Problems.

SPFA

ist die Warteschlangenoptimierung von Bellman-Ford, die eine relativ gute Aktualität und eine zeitliche Komplexität von O(kE) aufweist. (k<

Ähnlich wie der Bellman-Ford-Algorithmus verwendet der SPFA-Algorithmus eine Reihe von Entspannungsoperationen, um den kürzesten Pfad von einem Knoten zu allen anderen Knoten im Diagramm zu erhalten. Der Unterschied besteht darin, dass der SPFA-Algorithmus eine Warteschlange verwaltet, sodass nach der Aktualisierung des aktuell kürzesten Pfads eines Knotens keine Notwendigkeit besteht, andere Knoten sofort zu aktualisieren, wodurch die Anzahl wiederholter Vorgänge erheblich reduziert wird.

Weitere technische Artikel zum Thema PHP finden Sie in der Spalte PHP-Grafik-Tutorial, um mehr darüber zu erfahren!

Das obige ist der detaillierte Inhalt vonAlgorithmus für den kürzesten Weg. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!