Algoritma Floyd-Warshall adalah salah satu algoritma yang digunakan untuk pengambilan keputusan, tetapi bisa juga digunakan dalam pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur terpendek dengan biaya yang paling rendah.
Diasumsikan ada sebaran titik titik beraturan dalam sebuah grafik
Tidak semua titik terhubung satu sama lain, melainkan hanya melalui jalur-jalur tertentu saja
Dan setiap jalur memiliki biaya sendiri-sendiri
Tentukan Jalur yang harus diambil dari titik awal ke titik tujuan melalui jalur-jalur tertentu dengan biaya terendah
Dalam kasus ini, diasumsikan hanya ada 5×5 = 25 titik, dengan jalur sbb
| Titik Awal | Titik Tujuan | Biaya |
|---|---|---|
| 1 | 2 | 7 |
| 1 | 3 | 14 |
| 1 | 4 | 9 |
| 2 | 3 | 10 |
| 2 | 5 | 15 |
| 3 | 4 | 2 |
| 3 | 5 | 11 |
| 4 | 2 | 9 |
| 4 | 5 | 6 |
| 5 | 1 | 6 |
Langkah pertama adalah memasukkan data-data yang digunakan.
Contoh data adalah sebagai berikut
BiayaJalur(1, 2) = 7 BiayaJalur(1, 3) = 14 BiayaJalur(1, 4) = 9 BiayaJalur(2, 3) = 10 BiayaJalur(2, 5) = 15 BiayaJalur(3, 4) = 2 BiayaJalur(3, 5) = 11 BiayaJalur(4, 2) = 9 BiayaJalur(4, 5) = 6 BiayaJalur(5, 1) = 6
Langkah-langkah penggunaan algoritma ini adalah
1. Tentukan Titik Awal dan Titik Tujuan
Console.WriteLine("")
Console.WriteLine("Masukkan titik awal (1-5): ")
Dim awal As Integer = Console.ReadLine
Console.WriteLine("Masukkan titik tujuan (1-5): ")
Dim tujuan As Integer = Console.ReadLine
2. Isi Array Jalur dengan Biaya sesuai Array Biaya Jalur
For i As Integer = 1 To n For j As Integer = 1 To n If BiayaJalur(i, j) <> Infinity Then Jalur(i, j) = BiayaJalur(i, j) Else Jalur(i, j) = Infinity Next j Jalur(i, i) = 0 Next i
3. Lakukan pencarian pada semua titik awal dan titik tujuan
Ambil Jalur titik awal dengan titik tetangga dengan biaya terandah
For k As Integer = 1 To n For i As Integer = 1 To n For j As Integer = 1 To n If Jalur(i, k) + Jalur(k, j) < Jalur(i, j) Then Jalur(i, j) = Jalur(i, k) + Jalur(k, j) Next j Next i Next k
* Perlu diingat bahwa Algoritma Floyd Warshall pada umumnya hanya menghasilkan biaya terendah saja, tidak menghasilkan jalur yang harus ditempuh. Untuk mengembalikan jalur yang ditempuh untuk biaya tersebut, maka harus menambahkan sendiri penyimpanan data jalurnya. Contoh Algoritma Floyd-Warshall beserta pengembalian jalur yang ditempuh dapat didownload pada contoh modul dibawah.
Hasil akhir adalah: (klik untuk perbesar gambar)
Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:
Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.