Algoritma Floyd-Warshall: Contoh Perhitungan Jalur Terpendek Lengkap

Floyd-Warshall adalah algoritma untuk mencari jalur terpendek antara semua pasangan simpul pada sebuah graf berbobot. Berbeda dengan Dijkstra yang biasanya dijalankan dari satu simpul sumber, Floyd-Warshall langsung menghasilkan jarak minimum untuk setiap pasangan simpul dalam satu proses.

Algoritma ini menggunakan pendekatan dynamic programming. Pada setiap iterasi, sebuah simpul diperbolehkan menjadi simpul perantara, kemudian jarak antar dua simpul diperbarui jika jalur melalui simpul perantara tersebut lebih pendek.

Tutorial ini menggunakan contoh graf dengan empat simpul A, B, C, dan D. Perhitungan dilakukan mulai dari matriks jarak awal, iterasi melalui simpul A, B, C, dan D, hingga menghasilkan matriks shortest path akhir.

---

Daftar Isi

• Pengertian Floyd-Warshall
• Konsep All-Pairs Shortest Path
• Rumus Floyd-Warshall
• Cara Kerja Floyd-Warshall
• Representasi Graf dalam Matriks
• Contoh Kasus Floyd-Warshall
  • #01 Menentukan Graf
  • #02 Membentuk Matriks Awal D0
  • #03 Iterasi k = A
  • #04 Iterasi k = B
  • #05 Iterasi k = C
  • #06 Iterasi k = D
  • #07 Matriks Jarak Terpendek Akhir
  • #08 Menentukan Jalur A ke D
• Rekonstruksi Jalur
• Negative Edge dan Negative Cycle
• Pseudocode Floyd-Warshall
• Implementasi Konsep dengan Matriks
• Kompleksitas Floyd-Warshall
• Floyd-Warshall vs Dijkstra
• Floyd-Warshall vs Bellman-Ford
• Kelebihan dan Kekurangan
• Kapan Floyd-Warshall Cocok Digunakan?
• Kesalahan Umum Implementasi
• Ringkasan
• FAQ Floyd-Warshall
• Referensi
• Source Code Floyd-Warshall

---

Pengertian Floyd-Warshall

Floyd-Warshall adalah algoritma all-pairs shortest path, yaitu algoritma yang mencari jarak terpendek dari setiap simpul menuju setiap simpul lainnya.

Jika graf memiliki simpul:

A, B, C, D

maka Floyd-Warshall dapat menghasilkan jarak minimum untuk:

A → B
A → C
A → D

B → A
B → C
B → D

C → A
C → B
C → D

D → A
D → B
D → C

Selain jarak, implementasi dapat dikembangkan untuk menyimpan informasi jalur sehingga urutan simpul yang dilewati juga dapat diketahui.

---

Konsep All-Pairs Shortest Path

Masalah all-pairs shortest path mencari jarak minimum untuk seluruh pasangan simpul.

Jika jumlah simpul adalah:

maka terdapat hingga:

pasangan sumber dan tujuan yang perlu diketahui jaraknya.

Floyd-Warshall menggunakan sebuah matriks berukuran:

Setiap elemen:

menyimpan jarak terbaik yang saat itu diketahui dari simpul \(i\) menuju simpul \(j\).

---

Rumus Floyd-Warshall

Rumus utama Floyd-Warshall:

Keterangan:

• \(D_{ij}^{(k)}\) = jarak minimum dari \(i\) ke \(j\) setelah simpul ke-\(k\) diperbolehkan sebagai perantara,
• \(D_{ij}^{(k-1)}\) = jarak sebelumnya dari \(i\) ke \(j\),
• \(D_{ik}^{(k-1)} + D_{kj}^{(k-1)}\) = jarak dari \(i\) ke \(j\) jika melewati \(k\).

Dalam bentuk lebih sederhana:

Jika jalur melalui \(k\) lebih pendek, nilai lama diganti.

---

Cara Kerja Floyd-Warshall

Algoritma Floyd-Warshall bekerja dengan tiga perulangan:

for k = setiap simpul perantara
    for i = setiap simpul asal
        for j = setiap simpul tujuan
            periksa apakah i → k → j lebih pendek

Urutan konsepnya:

Matriks Awal
    ↓
Izinkan A sebagai perantara
    ↓
Izinkan B sebagai perantara
    ↓
Izinkan C sebagai perantara
    ↓
Izinkan D sebagai perantara
    ↓
Matriks Jarak Terpendek

Setiap iterasi memperluas kumpulan simpul yang boleh digunakan sebagai perantara.

---

Representasi Graf dalam Matriks

Untuk graf berbobot:

• diagonal diberi nilai 0,
• edge langsung diberi bobotnya,
• pasangan simpul tanpa edge langsung diberi nilai tak hingga.

Secara umum:

Simbol:

menunjukkan belum ada jalur yang diketahui.

---

Contoh Kasus Floyd-Warshall

Contoh menggunakan graf berarah dengan simpul:

A
B
C
D

#01 Menentukan Graf

Edge yang tersedia:

Visualisasi sederhana:

A ──3──> B
│        │
7        2
│        │
v        v
D <──1── C

B ──8──> A
C ──5──> A
D ──2──> A

Tujuan kita adalah mencari jarak minimum untuk seluruh pasangan simpul.

---

#02 Membentuk Matriks Awal D0

Matriks awal hanya menggunakan edge langsung.

Contoh:

A → B = 3

karena terdapat edge langsung.

Sedangkan:

A → C = ∞

karena belum terdapat edge langsung A ke C.

---

#03 Iterasi k = A

Sekarang simpul A diperbolehkan sebagai perantara.

Rumus:

Beberapa perubahan penting:

B ke D melalui A

Sebelumnya:

Melalui A:

Karena:

maka:

C ke B melalui A

Sebelumnya:

Melalui A:

Maka:

D ke B melalui A

Sebelumnya:

Melalui A:

Maka:

Setelah seluruh pasangan diperiksa:

---

#04 Iterasi k = B

Sekarang simpul B diperbolehkan sebagai perantara.

Rumus:

Perubahan penting:

A ke C melalui B

Sebelumnya:

Melalui B:

Maka:

D ke C melalui B

Sebelumnya:

Melalui B:

Maka:

Matriks setelah B menjadi perantara:

---

#05 Iterasi k = C

Sekarang simpul C diperbolehkan sebagai perantara.

Rumus:

Perubahan penting:

A ke D melalui C

Sebelumnya:

Melalui C:

Karena:

maka:

B ke A melalui C

Sebelumnya:

Melalui C:

Maka:

B ke D melalui C

Sebelumnya:

Melalui C:

Karena:

maka:

Matriks setelah C sebagai perantara:

---

#06 Iterasi k = D

Sekarang simpul D diperbolehkan sebagai perantara.

Rumus:

Perubahan penting:

B ke A melalui D

Sebelumnya:

Melalui D:

Maka:

C ke A melalui D

Sebelumnya:

Melalui D:

Karena:

maka:

C ke B melalui D

Sebelumnya:

Melalui D:

Maka:

Setelah semua pasangan diperiksa:

---

#07 Matriks Jarak Terpendek Akhir

Setelah semua simpul digunakan sebagai perantara, diperoleh matriks shortest path:

Interpretasi beberapa hasil:

A → C = 5
A → D = 6
B → A = 5
B → D = 3
C → A = 3
C → B = 6
D → C = 7

Nilai pada tabel merupakan jarak minimum setelah seluruh kemungkinan simpul perantara diperiksa.

---

#08 Menentukan Jalur A ke D

Matriks akhir menunjukkan:

Padahal edge langsung:

Jadi jalur langsung bukan jalur terbaik.

Dari proses sebelumnya:

diperoleh melalui B:

dengan:

Kemudian:

Sehingga jalur:

A → B → C → D

memiliki total:

Maka:

lebih pendek daripada jalur langsung:

---

Rekonstruksi Jalur

Matriks jarak hanya menyimpan nilai minimum. Jika ingin mengetahui urutan simpul yang dilewati, tambahkan matriks seperti:

next[i][j]

atau:

predecessor[i][j]

Contoh konsep matriks next:

Jika terdapat edge i → j:
    next[i][j] = j

Ketika jarak diperbarui melalui simpul \(k\):

dist[i][j] = dist[i][k] + dist[k][j]
next[i][j] = next[i][k]

Untuk membentuk jalur dari A ke D:

A
↓
next[A][D] = B
↓
B
↓
next[B][D] = C
↓
C
↓
next[C][D] = D
↓
D

Hasil:

A → B → C → D

Dengan demikian, Floyd-Warshall dapat dikembangkan agar menghasilkan jarak sekaligus rute.

---

Negative Edge dan Negative Cycle

Salah satu kelebihan Floyd-Warshall adalah dapat menangani edge dengan bobot negatif selama graf tidak memiliki negative cycle yang relevan.

Contoh edge negatif:

A → B = 4
B → C = -2

Edge negatif tidak otomatis menjadi masalah.

Masalah terjadi jika terdapat siklus dengan total bobot negatif.

Contoh:

A → B = 2
B → C = -5
C → A = 1

Total:

Karena bernilai negatif, jalur dapat terus mengelilingi siklus dan menghasilkan biaya semakin kecil.

Setelah Floyd-Warshall selesai, salah satu cara mendeteksi negative cycle adalah memeriksa diagonal:

Jika terdapat simpul dengan:

dist[i][i] < 0

maka terdapat negative cycle yang dapat dicapai dari simpul tersebut.

---

Pseudocode Floyd-Warshall

Pseudocode dasar:

dist = matriks jarak awal

for k = 0 sampai V - 1:

    for i = 0 sampai V - 1:

        for j = 0 sampai V - 1:

            if dist[i][k] + dist[k][j] < dist[i][j]:

                dist[i][j] =
                    dist[i][k] + dist[k][j]

return dist

Versi dengan pengecekan infinity:

for k:

    for i:

        for j:

            if dist[i][k] != INF
               and dist[k][j] != INF:

                candidate =
                    dist[i][k] + dist[k][j]

                if candidate < dist[i][j]:

                    dist[i][j] = candidate

Pengecekan infinity penting pada bahasa pemrograman yang menggunakan angka besar sebagai representasi INF.

---

Implementasi Konsep dengan Matriks

Struktur data yang umum digunakan:

dist[V][V]

Contoh matriks awal:

[
    [0,   3, INF, 7],
    [8,   0,   2, INF],
    [5, INF,   0, 1],
    [2, INF, INF, 0]
]

Setelah Floyd-Warshall:

[
    [0, 3, 5, 6],
    [5, 0, 2, 3],
    [3, 6, 0, 1],
    [2, 5, 7, 0]
]

Perubahan tersebut menunjukkan bahwa beberapa pasangan simpul memperoleh jalur yang lebih pendek setelah menggunakan simpul perantara.

---

Kompleksitas Floyd-Warshall

Floyd-Warshall memiliki tiga nested loop:

k
 └── i
      └── j

Jika jumlah simpul:

maka kompleksitas waktu:

Kompleksitas memori untuk matriks jarak:

Jika menggunakan matriks tambahan untuk rekonstruksi jalur, kebutuhan memori tetap berada pada orde:

Walaupun implementasinya sederhana, \(O(V^3)\) dapat menjadi mahal jika jumlah simpul sangat besar.

---

Floyd-Warshall vs Dijkstra

Jika seluruh pasangan simpul perlu diketahui, Floyd-Warshall dapat sangat praktis terutama pada graf dengan jumlah simpul tidak terlalu besar.

---

Floyd-Warshall vs Bellman-Ford

Pemilihan algoritma bergantung pada bentuk graf dan kebutuhan aplikasi.

---

Kelebihan dan Kekurangan

Kelebihan Floyd-Warshall

• Menghasilkan shortest path untuk seluruh pasangan simpul.
• Implementasi relatif sederhana.
• Menggunakan matriks yang mudah dipahami.
• Mendukung edge negatif selama tidak terdapat negative cycle.
• Dapat dikembangkan untuk rekonstruksi rute.
• Cocok untuk graf dengan jumlah simpul kecil hingga menengah.

Kekurangan Floyd-Warshall

• Kompleksitas waktu \(O(V^3)\).
• Membutuhkan matriks \(O(V^2)\).
• Kurang efisien untuk graf sangat besar dan jarang.
• Menghitung seluruh pasangan meskipun hanya satu rute yang dibutuhkan.
• Negative cycle membutuhkan penanganan khusus.
• Kesalahan inisialisasi nilai infinity dapat menghasilkan perhitungan yang salah.

---

Kapan Floyd-Warshall Cocok Digunakan?

Floyd-Warshall cocok digunakan ketika:

• membutuhkan jarak terpendek seluruh pasangan simpul;
• jumlah simpul tidak terlalu besar;
• data graf nyaman direpresentasikan dalam matriks;
• terdapat banyak query rute dari berbagai sumber ke berbagai tujuan;
• graf dapat memiliki edge negatif tetapi tidak memiliki negative cycle;
• atau membutuhkan solusi yang sederhana untuk all-pairs shortest path.

Contoh penerapan:

• pencarian jarak antarkota pada jaringan kecil,
• analisis jaringan,
• routing internal,
• pemetaan hubungan antarlokasi,
• optimasi rute pada graf berukuran terbatas,
• analisis konektivitas berbobot,
• dan pembelajaran algoritma graf.

---

Kesalahan Umum Implementasi

1. Diagonal tidak diinisialisasi 0

Untuk setiap simpul:

2. Tidak menggunakan infinity untuk edge yang tidak ada

Pasangan simpul tanpa edge langsung sebaiknya menggunakan:

atau konstanta INF yang aman.

3. Menjumlahkan nilai INF sembarangan

Jika INF direpresentasikan dengan integer sangat besar, penjumlahan dapat menyebabkan overflow.

Gunakan pengecekan:

if dist[i][k] != INF
and dist[k][j] != INF

4. Salah urutan loop

Loop simpul perantara \(k\) harus berada di paling luar:

for k
    for i
        for j

Bentuk lain dapat tidak merepresentasikan recurrence Floyd-Warshall yang sama.

5. Menganggap Floyd-Warshall hanya mencari satu rute

Floyd-Warshall menghitung seluruh pasangan simpul.

6. Mengabaikan negative cycle

Setelah proses selesai, periksa:

jika graf dapat memiliki bobot negatif.

7. Hanya menyimpan jarak padahal aplikasi membutuhkan rute

Jika perlu menampilkan urutan simpul, siapkan matriks next atau predecessor sejak awal.

---

Ringkasan

Pada contoh graf:

A → B = 3
A → D = 7
B → A = 8
B → C = 2
C → A = 5
C → D = 1
D → A = 2

matriks awal:

Setelah semua simpul digunakan sebagai perantara, diperoleh:

Contoh jalur:

A → D langsung = 7

Tetapi Floyd-Warshall menemukan:

A → B → C → D

dengan total:

Sehingga shortest path:

---

FAQ Floyd-Warshall

Apa itu algoritma Floyd-Warshall?

Floyd-Warshall adalah algoritma untuk mencari jarak terpendek antara seluruh pasangan simpul pada graf berbobot.

Apa jenis masalah yang diselesaikan Floyd-Warshall?

Floyd-Warshall menyelesaikan masalah all-pairs shortest path.

Apa rumus utama Floyd-Warshall?

Rumus dasarnya membandingkan jarak langsung \(i\rightarrow j\) dengan jarak yang melewati simpul \(k\):

dist[i][j] =
min(
    dist[i][j],
    dist[i][k] + dist[k][j]
)

Apa fungsi simpul k?

Simpul \(k\) adalah kandidat simpul perantara pada proses dynamic programming.

Apakah Floyd-Warshall dapat menggunakan bobot negatif?

Bisa, selama tidak terdapat negative cycle yang membuat shortest path tidak terdefinisi.

Bagaimana mendeteksi negative cycle?

Setelah algoritma selesai, periksa diagonal matriks. Jika terdapat:

dist[i][i] < 0

maka terdapat negative cycle yang dapat memengaruhi simpul tersebut.

Berapa kompleksitas Floyd-Warshall?

Kompleksitas waktunya:

dan kebutuhan memori dasarnya:

Apakah Floyd-Warshall sama dengan Dijkstra?

Tidak. Floyd-Warshall menghitung seluruh pasangan simpul, sedangkan Dijkstra biasanya mencari shortest path dari satu sumber dan tidak mendukung edge negatif.

Apakah Floyd-Warshall dapat menampilkan rute?

Bisa. Tambahkan matriks next atau predecessor untuk menyimpan informasi jalur ketika jarak diperbarui.

Mengapa nilai awal menggunakan infinity?

Infinity menandakan bahwa pada tahap awal belum diketahui jalur langsung antara dua simpul.

Mengapa diagonal bernilai 0?

Karena jarak sebuah simpul menuju dirinya sendiri adalah 0 selama tidak mempertimbangkan negative cycle.

Apakah Floyd-Warshall termasuk dynamic programming?

Ya. Floyd-Warshall membangun solusi secara bertahap berdasarkan kumpulan simpul perantara yang diperbolehkan.

Kapan lebih baik menggunakan Floyd-Warshall daripada Dijkstra?

Floyd-Warshall cocok ketika jarak terpendek untuk banyak atau seluruh pasangan simpul diperlukan dan ukuran graf masih memungkinkan kompleksitas \(O(V^3)\).

Apakah Floyd-Warshall cocok untuk graf tidak berarah?

Bisa. Untuk graf tidak berarah, masukkan bobot pada kedua arah:

A → B
B → A

dengan bobot yang sama jika edge memang simetris.

---

Referensi

1. Floyd, R. W. (1962). Algorithm 97: Shortest Path. Communications of the ACM, 5(6), 345.
2. Warshall, S. (1962). A Theorem on Boolean Matrices. Journal of the ACM, 9(1), 11–12.
3. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms. Fourth Edition. MIT Press.

---

Source Code Floyd-Warshall

Berikut source code yang menggunakan algoritma Floyd-Warshall pada RumahSourceCode.

Source Code TSP Metode Greedy dan Floyd Warshall PHP

Rp350,000