Deutsch
Deutsch
In der Graphentheorie ist das kürzeste Pfadproblem ein klassisches algorithmisches Problem, das den kürzesten Pfad zwischen zwei Scheitelpunkten in gerichteten oder ungerichteten Graphen beinhaltet. Der Floyd-Warshall-Algorithmus ist ein klassischer dynamischer Programmieralgorithmus zur Lösung dieses Problems. In diesem Artikel wird ausführlich erklärt, wie der Floyd-Warshall-Algorithmus mit PHP implementiert wird.
Der Floyd-Warshall-Algorithmus ist ein Algorithmus, der das kürzeste Pfadproblem löst, indem die kürzesten Pfadlängen zwischen allen Scheitelpunkten in einem Diagramm iterativ verglichen werden. Es verwendet ein zweidimensionales Array, um die kürzeste Pfadlänge zwischen Scheitelpunkten zu speichern und dieses Array in jeder Iteration zu aktualisieren. Schließlich können wir den kürzesten Weg zwischen allen Scheitelpunkten erreichen.
Zunächst müssen wir ein 2D -Array von n x n erstellen, wobei N die Anzahl der Scheitelpunkte im Diagramm darstellt. Jedes Element im Array repräsentiert den Abstand zwischen zwei Eckpunkten, und wenn es keine Kanten zwischen den beiden Scheitelpunkten gibt, ist der Abstand auf unendlich eingestellt. Das Folgende ist die Implementierung von PHP -Code:
Funktion flydwarshall ($ graph) {
$ n = count ($ graph);
$ dist = $ graph;
für ($ k = 0; $ k <$ n; $ k ++) {
für ($ i = 0; $ i <$ n; $ i ++) {
für ($ j = 0; $ j <$ n; $ j ++) {
if ($ dist [$ i] [$ k] + $ dist [$ k] [$ j] <$ dist [$ i] [$ j]) {
$ dist [$ i] [$ j] = $ dist [$ i] [$ k] + $ dist [$ k] [$ j];
}
}
}
}
Return $ dist;
}
Als nächstes definieren wir ein Beispielgrafik und testen unseren Algorithmus. Wir verwenden eine Adjazenzmatrix, um die Struktur des Diagramms darzustellen und den Abstand zwischen Scheitelpunkten in einem zweidimensionalen Array zu speichern. Der Beispielcode lautet wie folgt:
$ graph = [
[0, 5, Inf, 10],
[Inf, 0, 3, Inf],
[Inf, Inf, 0, 1],
[Inf, Inf, Inf, 0]
];
In der obigen Beispieldiagramm bedeutet Inf, dass zwischen zwei Scheitelpunkten keine Kante vorhanden ist, und wir setzen seinen Abstand auf einen sehr großen Wert. Jetzt können wir die Floydwarshall -Funktion aufrufen, um das kürzeste Pfadarray zu berechnen.
$ result = floydwarshall ($ graph);
Führen Sie den obigen Code aus und wir erhalten das folgende Ergebnis:
0 5 8 9 Inf 0 3 4 Inf Inf 0 1 Inf Inf Inf 0
Die obigen Ergebnisse zeigen die kürzeste Pfadlänge zwischen allen Scheitelpunkten in der Abbildung. Wobei Inf bedeutet, dass zwischen zwei Scheitelpunkten keine Pfadverbindung besteht.
In diesem Artikel wird vorgestellt, wie der Floyd-Warshall-Algorithmus mithilfe von PHP implementiert wird, um das kürzeste Pfadproblem von Graphen zu lösen. Durch die Verwendung der Idee der dynamischen Programmierung können wir die kürzeste Pfadlänge zwischen allen Scheitelpunkten im Diagramm mit einer zeitlichen Komplexität von O (n^3) finden. Durch die Verwendung von Algorithmus -Designtechniken können wir diesen Algorithmus schnell und effizient bei der Lösung praktischer Probleme anwenden.
