Bagaimana untuk melaksanakan algoritma Floyd-Warshall menggunakan Python?

Bagaimana untuk melaksanakan algoritma Floyd-Warshall menggunakan Python?

Algoritma Floyd-Warshall ialah algoritma klasik yang digunakan untuk menyelesaikan masalah laluan terpendek dari semua titik sumber ke semua titik destinasi. Ia ialah algoritma pengaturcaraan dinamik yang boleh digunakan untuk menangani graf terarah atau masalah kelebihan berat negatif. Artikel ini akan memperkenalkan cara menggunakan Python untuk melaksanakan algoritma Floyd-Warshall dan memberikan contoh kod khusus.

Idea teras algoritma Floyd-Warshall adalah untuk mengemas kini laluan terpendek antara nod secara beransur-ansur dengan merentasi semua nod dalam graf, menggunakan setiap nod sebagai nod perantaraan. Kita boleh menggunakan matriks dua dimensi untuk menyimpan jarak antara nod dalam graf.

Pertama, kita perlu menentukan fungsi untuk melaksanakan algoritma Floyd-Warshall. Berikut ialah rangka kerja algoritma mudah:

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

Kod ini menggunakan tiga gelung bersarang untuk memproses setiap nod dalam graf. Dalam setiap lelaran, kami mencari laluan yang lebih pendek dengan mengemas kini matriks jarak. Secara khusus, kami akan menyemak sama ada laluan dari nod i ke nod j boleh mencapai jarak yang lebih pendek melalui nod k. Jika ya, kami mengemas kini nilai dalam matriks jarak.

Sebelum menggunakan fungsi ini, kita perlu mentakrifkan graf. Berikut ialah takrifan contoh graf:

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

Graf contoh ini ialah perwakilan matriks bersebelahan bagi graf terarah. Antaranya, float('inf') bermaksud jarak tidak terhingga, yang bermaksud tiada sambungan langsung antara kedua-dua nod. 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]

Di bawah, kami memanggil fungsi floydWarshall, hantar dalam graf sebagai parameter dan cetak hasil akhir:

rrreee

Kod lengkap adalah seperti berikut: 🎜rrreee🎜Jalankan kod di atas, anda akan mendapat output berikut: 🎜 Hasil output rrreee🎜 ialah matriks dua dimensi yang mewakili laluan terpendek antara mana-mana dua nod dalam graf. Sebagai contoh, nilai result[0][2] ialah -2, yang bermaksud jarak laluan terpendek dari nod 0 ke nod 2 ialah -2. Jika dua nod tidak boleh dicapai, jarak ditandakan sebagai infiniti. 🎜🎜Melalui contoh ini, kita dapat memahami dengan jelas pelaksanaan dan penggunaan algoritma Floyd-Warshall. Saya harap artikel ini dapat membantu anda memahami dan menggunakan algoritma ini! 🎜

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma Floyd-Warshall menggunakan Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!