Floyd Warshall Algorithm

SedangJalur terpendek Dynamic programming

+10

Graf berarah dengan n node yang diberi nomor dari 0 hingga n-1 diberikan sebagai matriks berukuran n kali n: matrix[i][j] adalah bobot sisi dari node i ke node j, atau -1 jika tidak ada sisi, dan matrix[i][i] adalah 0. Panjang suatu jalur adalah jumlah bobot sisi-sisinya.

Kembalikan matriks berukuran n kali n dengan entri [i][j] berupa panjang jalur terpendek dari node i ke node j, atau -1 jika node j tidak dapat dicapai dari node i.

Fungsi

shortestDistances(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: bobot sisi: matrix[i][j] adalah bobot sisi dari i ke j, atau -1 jika tidak ada
Mengembalikaninteger-2d-array: jarak terpendek untuk setiap pasangan simpul, -1 jika tidak ada jalur

Batasan

1 ≤ n ≤ 100, dengan n = matrix.length = matrix[i].length
matrix[i][i] = 0
Untuk i ≠ j, matrix[i][j] bernilai -1 (tidak ada sisi) atau 0 ≤ matrix[i][j] ≤ 1000.
Edge hanya memiliki satu arah: matrix[i][j] dan matrix[j][i] tidak saling bergantung.

Contoh

Input: matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]
Output: [[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]
Penjelasan: Melalui node 1, node 0 mencapai node 2 dengan jarak 6, bukan 11, dan node 3 dengan jarak 9. Node 1 mencapai node 0 melalui node 2 dengan jarak 3. Tidak ada jalur yang keluar dari node 3, jadi nilainya -1 pada baris tersebut di luar diagonal.

Input: matrix = [[0, 6, 1], [-1, 0, -1], [-1, 0, 0]]
Output: [[0, 1, 1], [-1, 0, -1], [-1, 0, 0]]
Penjelasan: Sisi dari 2 ke 1 memiliki bobot 0, jadi 0 → 2 → 1 berbiaya 1, lebih kecil daripada biaya langsung 6. Tidak ada sisi yang keluar dari simpul 1 atau masuk ke simpul 0, jadi pasangan tersebut tetap -1.

Pertanyaan lanjutan

Setelah kamu membangun tabel, satu sisi menjadi lebih murah. Bisakah kamu memperbarui setiap jarak dalam O(n²) alih-alih menjalankan ulang perulangan O(n³)?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Kamu perlu mencari jalur terpendek untuk setiap pasangan node. Floyd-Warshall menemukan semua n² jawaban dengan satu perulangan tiga tingkat. Setiap putaran memungkinkan rute melewati satu node tambahan dan memerlukan satu perbandingan untuk setiap pasangan: rute terbaik sejauh ini dibandingkan dengan rute yang melewati node baru.

Perpanjang setiap rute dengan satu sisi hingga tidak ada perubahan

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Mulai dari matriks, lalu pada setiap iterasi, perpanjang setiap rute dengan satu sisi: rute dari i ke m ditambah sisi m → j menjadi rute dari i ke j, dan dipertahankan jika lebih pendek. Ulangi hingga tidak ada perubahan dalam satu iterasi.

Setelah p iterasi, setiap rute terpendek dengan hingga p+1 sisi telah ditemukan. Tidak ada bobot yang negatif, jadi beberapa rute terpendek tidak memiliki perulangan dan memiliki paling banyak n-1 sisi, lalu iterasi berhenti setelah semua jarak mencapai nilai akhir. Satu iterasi membutuhkan n³ = 10^6 langkah untuk 100 node, dan rangkaian panjang rute terpendek membutuhkan hingga n iterasi: O(n⁴), hingga 10^8 langkah.

Algoritma

Salin matrix ke dalam dist.
Untuk setiap i, m, dan j: jika dist[i][m] dan matrix[m][j] keduanya ada, hitung jumlahnya.
Jika dist[i][j] adalah -1 atau lebih besar daripada jumlah tersebut, simpan jumlah tersebut dan ingat bahwa proses ini mengubah sesuatu.
Ulangi proses ini sampai tidak ada perubahan, lalu kembalikan dist.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the routes of one edge; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    changed = True
    while changed:
        changed = False
        # One pass: a route from i that ends at m may grow by the edge m -> j.
        for i in range(n):
            for m in range(n):
                if dist[i][m] == -1:
                    continue
                for j in range(n):
                    edge = matrix[m][j]
                    if edge == -1:
                        continue
                    via = dist[i][m] + edge
                    if dist[i][j] == -1 or via < dist[i][j]:
                        dist[i][j] = via
                        changed = True
    return dist

Floyd-Warshall: izinkan satu pemberhentian lagi pada setiap putaran

Intuisi

Batasi node yang boleh menjadi tempat berhenti bagi rute di antara kedua ujungnya. Tabel dimulai sebagai matriks, yaitu rute tanpa tempat berhenti. Setelah putaran k, dist[i][j] adalah rute terpendek yang semua tempat berhentinya berada di antara node 0 hingga k, dan putaran terakhir memberikan jawabannya.

Pada putaran k, rute terbaik yang juga boleh berhenti di k bisa melewati k begitu saja, dan tabel sudah menyimpan rute itu, atau melewati k satu kali, karena tidak ada bobot yang negatif. Kedua bagiannya hanya berhenti di node 0 hingga k-1, jadi keduanya adalah dist[i][k] dan dist[k][j].

Pada contoh pertama, putaran 1 mengganti jarak langsung 11 dari node 0 ke node 2 dengan 6. Putaran 2 menghasilkan jarak dari node 0 ke node 3 sebesar 6 + 3 = 9, dengan tempat berhenti di node 1 berada di dalam rute bernilai 6.

Satu tabel saja sudah cukup: baris k dan kolom k tidak berubah pada putaran k, karena dist[k][k] bernilai 0.

Algoritma

Salin matrix ke dist; -1 berarti rute belum ditemukan.
Untuk k dari 0 hingga n-1, dan untuk setiap i dan j: lewati pasangan jika dist[i][k] atau dist[k][j] bernilai -1.
Jika tidak, hitung via = dist[i][k] + dist[k][j].
Jika dist[i][j] bernilai -1 atau lebih besar daripada via, tetapkan nilainya menjadi via.
Kembalikan dist.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the direct edges; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    # After round k, dist[i][j] is the cheapest route whose stops all lie in 0..k.
    for k in range(n):
        for i in range(n):
            if dist[i][k] == -1:
                continue
            for j in range(n):
                if dist[k][j] == -1:
                    continue
                via = dist[i][k] + dist[k][j]
                if dist[i][j] == -1 or via < dist[i][j]:
                    dist[i][j] = via
    return dist

Jebakan dan kasus tepi

Menambahkan -1 seolah-olah itu bobot: -1 + 5 = 4 tampak seperti rute. Periksa kedua bagian terlebih dahulu, dan perlakukan -1 dalam dist[i][j] sebagai sesuatu yang lebih buruk daripada rute mana pun.
Menempatkan perulangan untuk k di bagian dalam. Rute melalui pemberhentian 0 hingga k-1 harus sudah final sebelum node k ditawarkan.
Menggunakan int terbesar sebagai tak terhingga: menjumlahkan dua nilai akan menyebabkan int 32-bit overflow hingga menghasilkan jarak negatif. Jarak sebenarnya paling banyak 99 × 1000 = 99,000, jadi 10^9 aman, karena 2 × 10^9 lebih kecil daripada 2^31-1.
Menganggap edge berjalan ke dua arah. Pada contoh kedua, node 0 dapat mencapai node 1, tetapi node 1 tidak dapat mencapai node mana pun.
Menjalankan breadth-first search, yang mengabaikan bobot: pada contoh pertama, hasilnya adalah 11 dari node 0 ke node 2, bukan 6.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu algoritma Floyd Warshall?

Waktu O(n³) untuk n node: tiga perulangan bersarang pada node, dengan satu penjumlahan dan satu perbandingan per langkah, 10^6 langkah untuk 100 node. Ruang yang dibutuhkan adalah O(n²) untuk tabel jarak, yang dapat diperbarui secara langsung.

Apakah Floyd Warshall berfungsi dengan bobot sisi negatif?

Ya, selama tidak ada siklus negatif, yaitu perulangan yang jumlah bobotnya kurang dari 0. Jika ada siklus negatif, jalur terpendek tidak terdefinisi, dan tabel menunjukkannya: beberapa dist[i][i] bernilai kurang dari 0.

Kapan kamu sebaiknya menggunakan Floyd Warshall alih-alih algoritma Dijkstra?

Gunakan Floyd-Warshall untuk setiap pasangan simpul dalam graf padat dengan hingga beberapa ratus simpul. Dijkstra dari setiap simpul memerlukan biaya O(n³) dengan array dan O(n · E log n) dengan heap, yang lebih unggul pada graf jarang berukuran besar. Floyd-Warshall tidak memerlukan heap dan menerima sisi berbobot negatif, sedangkan Dijkstra tidak.

def shortestDistances(matrix):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]

Output yang diharapkan

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