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 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


Langkah-langkah penggunaan algoritma ini adalah

1. Tentukan Titik Awal dan Titik Tujuan

2. Isi Array Jalur dengan Biaya sesuai Array Biaya Jalur

3. Lakukan pencarian pada semua titik awal dan titik tujuan
Ambil Jalur titik awal dengan titik tetangga dengan biaya terandah

* 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 *