Penjelasan algoritma Floyd-Warshall: cara kerja, kode, dan kompleksitas

Masalah yang diselesaikan Floyd-Warshall

Kadang Anda membutuhkan jarak antara semua pasangan tempat, bukan hanya dari satu titik awal: tabel waktu tempuh antar semua kota, latensi antara setiap pasangan server, atau keterjangkauan penuh pada graf dependensi. Floyd-Warshall menyelesaikan masalah all-pairs shortest path ini dengan algoritma dynamic programming yang sangat singkat.

Algoritma ini diterbitkan oleh Robert Floyd pada 1962 ("Algorithm 97: Shortest path"), dengan dasar algoritma transitive closure dari Stephen Warshall pada tahun 1962.

Ide dasar dengan kata-kata sederhana

Beri nomor node dari 0 sampai V − 1. Setelah memproses node k, dist[i][j] adalah jalur terpendek dari i ke j yang hanya memakai node 0 sampai k sebagai perhentian antara. Mengizinkan satu node antara lagi, yaitu k, memberi dua pilihan: jalur terbaik lama yang menghindari k, atau jalur i → k → j yang terdiri dari dua jalur terbaik yang hanya memakai node sebelum k.

1. Isi matriks: 0 di diagonal, bobot edge jika edge ada, tak hingga di tempat lain.
2. Untuk k = 0 sampai V − 1, untuk setiap pasangan (i, j): jika dist[i][k] + dist[k][j] < dist[i][j], perbarui.
3. Setelah k terakhir, matriks berisi semua jarak terpendek. Nilai negatif di diagonal berarti ada siklus negatif.

Urutan loop sangat penting: k harus menjadi loop terluar.

Contoh langkah demi langkah

Graf berarah dengan 4 node dan edge 0→1 (3), 0→3 (7), 1→0 (8), 1→2 (2), 2→0 (5), 2→3 (1), 3→0 (2). Matriks awal (baris = asal, kolom = tujuan):

1. k = 0: jalur boleh melewati node 0. 1→3 menjadi 8 + 7 = 15, 2→1 menjadi 5 + 3 = 8, dan 3→1 menjadi 2 + 3 = 5.
2. k = 1: lewat node 1. 0→2 menjadi 3 + 2 = 5 dan 3→2 menjadi 5 + 2 = 7.
3. k = 2: lewat node 2. 0→3 membaik dari 7 menjadi 5 + 1 = 6, 1→3 dari 15 menjadi 2 + 1 = 3, dan 1→0 dari 8 menjadi 2 + 5 = 7.
4. k = 3: lewat node 3. 1→0 membaik dari 7 menjadi 3 + 2 = 5, 2→0 dari 5 menjadi 1 + 2 = 3, dan 2→1 dari 8 menjadi 1 + 5 = 6.

Baris matriks akhir: 0 → [0, 3, 5, 6], 1 → [5, 0, 2, 3], 2 → [3, 6, 0, 1], 3 → [2, 5, 7, 0].

Implementasi Python

INF = float("inf")
def floyd_warshall(n, edges):
    dist = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    nxt = [[j if i == j else None for j in range(n)] for i in range(n)]
    for u, v, w in edges:
        dist[u][v] = w
        nxt[u][v] = v
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    nxt[i][j] = nxt[i][k]
    return dist, nxt
edges = [(0, 1, 3), (0, 3, 7), (1, 0, 8), (1, 2, 2),
         (2, 0, 5), (2, 3, 1), (3, 0, 2)]
dist, nxt = floyd_warshall(4, edges)
for row in dist:
    print(row)
# [0, 3, 5, 6]
# [5, 0, 2, 3]
# [3, 6, 0, 1]
# [2, 5, 7, 0]

Matriks nxt menyimpan langkah pertama pada jalur terbaik dari i ke j, yang cukup untuk merekonstruksi jalur apa pun:

def path(nxt, i, j):
    if nxt[i][j] is None:
        return []                         # no path
    route = [i]
    while i != j:
        i = nxt[i][j]
        route.append(i)
    return route
print(path(nxt, 1, 0))  # [1, 2, 3, 0]

Jika node banyak dan Anda menginginkan kecepatan di Python, triple loop yang sama dapat ditulis dengan NumPy sebagai satu pembaruan vektor per k: d = np.minimum(d, d[:, k, None] + d[None, k, :]).

Kompleksitas waktu dan ruang

Untuk graf jarang dengan bobot non-negatif, menjalankan Dijkstra dari setiap node berbiaya O(V × (V + E) log V), yang lebih cepat daripada O(V³) bila E jauh lebih kecil daripada V².

Varian dan kesalahan umum

• Siklus negatif: setelah loop selesai, jika dist[i][i] < 0 untuk suatu i, node i berada pada siklus negatif dan jalur terpendek yang melewatinya tidak terdefinisi.
• Transitive closure (Warshall): gunakan boolean dan ganti min/plus dengan or/and: reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]).
• Jalur minimax dan maximin: ganti + dengan max (atau min) untuk mencari, misalnya, jalur yang edge terbesarnya sekecil mungkin.
• Pakai bilangan terbatas yang besar sebagai pengganti tak hingga hanya jika Anda yakin jumlah dua bilangan itu tidak overflow; di Python, float("inf") adalah pilihan aman.
• Inisialisasi diagonal dengan 0, dan bila ada edge paralel simpan bobot terkecil.

Kapan memakainya dan penggunaannya di dunia nyata

• Menghitung di muka tabel jarak antara semua stasiun, gudang, atau kota untuk pencarian berikutnya.
• Analitik graf seperti closeness centrality atau diameter jaringan kecil.
• Soal wawancara: mencari kota dengan jumlah tetangga paling sedikit dalam batas jarak, evaluate division (rasio sebagai hasil kali jalur), prasyarat mata kuliah sebagai transitive closure.