Wie implementiert man den Floyd-Warshall-Algorithmus mit Python?

Wie implementiert man den Floyd-Warshall-Algorithmus mit Python?

Der Floyd-Warshall-Algorithmus ist ein klassischer Algorithmus zur Lösung des Problems des kürzesten Pfades von allen Quellpunkten zu allen Zielpunkten. Es handelt sich um einen dynamischen Programmieralgorithmus, der zur Behandlung von gerichteten Graphen oder Problemen mit Kanten mit negativem Gewicht verwendet werden kann. In diesem Artikel wird die Verwendung von Python zur Implementierung des Floyd-Warshall-Algorithmus vorgestellt und spezifische Codebeispiele bereitgestellt.

Die Kernidee des Floyd-Warshall-Algorithmus besteht darin, den kürzesten Pfad zwischen Knoten schrittweise zu aktualisieren, indem alle Knoten im Diagramm durchlaufen werden und jeder Knoten als Zwischenknoten verwendet wird. Wir können eine zweidimensionale Matrix verwenden, um den Abstand zwischen Knoten im Diagramm zu speichern.

Zuerst müssen wir eine Funktion definieren, um den Floyd-Warshall-Algorithmus zu implementieren. Das Folgende ist ein einfaches Algorithmus-Framework:

def floydWarshall(graph):
    dist = graph
    num_vertices = len(graph)
    
    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

Dieser Code verwendet drei verschachtelte Schleifen, um jeden Knoten im Diagramm zu verarbeiten. In jeder Iteration finden wir kürzere Pfade, indem wir die Distanzmatrix aktualisieren. Insbesondere prüfen wir, ob der Pfad vom Knoten i zum Knoten j eine kürzere Distanz durch Knoten k erreichen kann. Wenn ja, aktualisieren wir den Wert in der Distanzmatrix.

Bevor wir diese Funktion verwenden, müssen wir ein Diagramm definieren. Das Folgende ist die Definition eines Beispielgraphen:

graph = [
    [0, float('inf'), -2, float('inf')],
    [4, 0, 3, float('inf')],
    [float('inf'), float('inf'), 0, 2],
    [float('inf'), -1, float('inf'), 0]
]

Dieser Beispielgraph ist eine Adjazenzmatrixdarstellung eines gerichteten Graphen. Unter diesen bedeutet float('inf'), dass der Abstand unendlich ist, was bedeutet, dass zwischen den beiden Knoten keine direkte Verbindung besteht. float('inf')表示距离为无穷大，这意味着两个节点之间没有直接连接。

下面，我们调用floydWarshall函数，传入图作为参数，并打印最终的结果：

result = floydWarshall(graph)
for row in result:
    print(row)

完整的代码如下：

def floydWarshall(graph):
    dist = graph
    num_vertices = len(graph)
    
    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

graph = [
    [0, float('inf'), -2, float('inf')],
    [4, 0, 3, float('inf')],
    [float('inf'), float('inf'), 0, 2],
    [float('inf'), -1, float('inf'), 0]
]

result = floydWarshall(graph)
for row in result:
    print(row)

运行上述代码，你会得到以下输出：

[0, -1, -2, 0]
[4, 0, 2, 4]
[5, 1, 0, 2]
[3, -1, 1, 0]

输出的结果是一个二维矩阵，表示图中任意两个节点之间的最短路径。例如，result[0][2]

Nachfolgend rufen wir die Funktion floydWarshall auf, übergeben das Diagramm als Parameter und drucken das Endergebnis aus:

rrreee

Der vollständige Code lautet wie folgt: 🎜rrreee🎜Führen Sie den obigen Code aus erhält die folgende Ausgabe: 🎜 Das Ausgabeergebnis von rrreee🎜 ist eine zweidimensionale Matrix, die den kürzesten Pfad zwischen zwei beliebigen Knoten im Diagramm darstellt. Der Wert von result[0][2] ist beispielsweise -2, was bedeutet, dass die kürzeste Pfadentfernung von Knoten 0 zu Knoten 2 -2 beträgt. Wenn zwei Knoten nicht erreichbar sind, wird die Entfernung als unendlich markiert. 🎜🎜Anhand dieses Beispiels können wir die Implementierung und Verwendung des Floyd-Warshall-Algorithmus klar verstehen. Ich hoffe, dieser Artikel kann Ihnen helfen, diesen Algorithmus zu verstehen und anzuwenden! 🎜

Das obige ist der detaillierte Inhalt vonWie implementiert man den Floyd-Warshall-Algorithmus mit Python?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!