Bandingkan pelaksanaan penutupan transitif algoritma Floyd-Warshall dan algoritma Warshall

Fahami dua algoritma penutupan transitif: Algoritma Floyd-Warshall vs algoritma Warshall

Penutupan transitif ialah konsep penting dalam teori graf, menerangkan hubungan transitif antara nod dalam graf. Algoritma penutupan transitif boleh membantu kami menentukan dengan cepat sama ada terdapat laluan dari titik A ke titik B dalam graf.

Dalam algoritma penutupan transitif, terdapat dua algoritma yang biasa digunakan: algoritma Floyd-Warshall dan algoritma Warshall. Kedua-duanya dapat mengira penutupan transitif dengan cekap, tetapi berbeza dalam butiran pelaksanaan dan prestasi.

1. Algoritma Floyd-Warshall

Algoritma Floyd-Warshall ialah algoritma pengaturcaraan dinamik yang digunakan untuk mengira laluan terpendek antara mana-mana dua titik dalam graf. Algoritma Floyd-Warshall secara berterusan mengemas kini jarak antara nod dengan merentasi semua nod dalam graf Dalam matriks akhir, jika terdapat laluan dari nod i ke nod j, maka kedudukan (i, j) dalam Nilai matriks ialah 1. , jika tidak 0.

Berikut ialah contoh kod untuk algoritma Floyd-Warshall:

def floyd_warshall(graph):
    n = len(graph)
    dist = [[float('inf')] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if i == j:
                dist[i][j] = 0
            elif graph[i][j] != 0:
                dist[i][j] = graph[i][j]

    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    return dist

2. Algoritma Warsshall

Algoritma Warshall ialah algoritma berdasarkan operasi matriks, digunakan untuk mengira sama ada terdapat laluan antara mana-mana dua titik dalam graf. Dengan mengemas kini matriks Boolean secara berterusan, hubungan transitif dalam graf ditentukan.

Berikut ialah contoh kod algoritma Warshall:

def warshall(graph):
    n = len(graph)
    reachable = [[False] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if graph[i][j] != 0:
                reachable[i][j] = True

    for k in range(n):
        for i in range(n):
            for j in range(n):
                reachable[i][j] = reachable[i][j] or (reachable[i][k] and reachable[k][j])

    return reachable

Melalui kod sampel di atas, kami memahami pelaksanaan khusus algoritma Floyd-Warshall dan algoritma Warshall. Kedua-duanya mempunyai kecekapan tinggi dalam mengira penutupan transitif, tetapi algoritma Floyd-Warshall sesuai untuk mengira laluan terpendek antara mana-mana dua titik dalam graf terarah, manakala algoritma Warshall sesuai untuk menentukan sama ada mana-mana dua titik dalam graf adalah Laluan wujud.

Apabila kita perlu mengira laluan terpendek, kita boleh menggunakan algoritma Floyd-Warshall; dan apabila kita hanya perlu menentukan sama ada laluan wujud, kita boleh memilih algoritma Warshall. Dengan memilih algoritma yang sesuai, kami boleh menyelesaikan pengiraan penutupan transitif dalam masalah teori graf dengan lebih cekap.

Atas ialah kandungan terperinci Bandingkan pelaksanaan penutupan transitif algoritma Floyd-Warshall dan algoritma Warshall. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!