Algoritma Floyd-Warshall


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 AwalTitik TujuanBiaya
127
1314
149
2310
2515
342
3511
429
456
516

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)

cmd12a

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.

Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *