ANALISIS ALGORITMA FLOYD UNTUK MENYELESAIKAN MASALAH PENCARIAN LINTASAN TERPENDEK PADA SETIAP PASANGAN SIMPUL

Syurya Pratiningsih, Neva Satyahadewi, Bayu Prihandono

Abstract


Penentuan lintasan terpendek dapat dilakukan dengan beberapa algoritma, salah satunya dengan Algoritma Floyd. Algoritma Floyd merupakan algoritma perhitungan untuk mencari lintasan terpendek pada setiap pasangan simpul (all pairs shortest path). Tujuan dari penelitian ini adalah mengkaji dan mengaplikasikan Algoritma Floyd untuk menentukan lintasan terpendek setiap pasangan simpul. Salah satu penerapan Algoritma Floyd digunakan untuk menentukan lintasan terpendek antar tempat kunjungan wisata di Kota Singkawang. Pencarian lintasan terpendek menggunakan Algoritma Floyd dimaksudkan untuk meminimalisir kemungkinan wisatawan berputar-putar mengitari Kota Singkawang. Daftar nama tempat wisata diperoleh dari Dinas Kebudayaan, Pariwisata, Pemuda dan Olahraga Kota Singkawang dan data besarnya jarak antar tempat kunjungan wisata diperoleh dari Dinas Bina Marga Kota Singkawang dan bantuan Google Map. Data bobot diinterpretasikan ke dalam bentuk matriks , dimana merupakan jumlah simpul. Matriks pendahulu (predecessor) kemudian dibentuk untuk mendapatkan lintasan terpendek pada iterasi 1. Setelah itu dilakukan iterasi sebanyak . Penentuan bobot lintasan terpendek adalah nilai dari setiap elemen pada matriks bobot. Sehingga lintasan yang dilalui dari simpul awal ke simpul tujuan diberikan oleh matriks pendahulu. Lintasan terpendek yang diperoleh untuk menempuh semua simpul dengan salah satu simpul boleh dilewati kembali adalah dengan panjang lintasannya 110,7 km.

Kata kunci : lintasan terpendek, algoritma Floyd, matriks, simpul

Full Text:

PDF


DOI: http://dx.doi.org/10.26418/bbimst.v5i01.14893

Refbacks

  • There are currently no refbacks.