PENCARIAN LINTASAN TERPENDEK DENGAN MENGGUNAKAN ALGORITMA BELLMAN-FORD

Abstract

Pencarian lintasan terpendek dari satu titik ke titik yang lain adalah masalah yang sering ditemui dalam kehidupan. Dalam teori graf, persoalan lintasan terpendek merupakan suatu persoalan untuk mencari lintasan antara dua buah titik pada graf berbobot yang memiliki gabungan nilai jumlah bobot pada sisi graf yang dilalui dengan jumlah yang paling minimum. Salah satu algoritma untuk menentukan lintasan terpendek adalah algoritma Bellman-Ford. Algoritma ini dapat digunakan dalam graf untuk bobot yang dapat bernilai positif ataupun bernilai negatif dan digunakan dalam graf berarah saja. Permasalahan yang dibahas adalah pencarian lintasan terpendek dengan menggunakan algoritma Bellman- Ford studi kasus pada kunjungan wisata yang ada di Kabupaten dan Kota Probolinggo. Dalam menyelesaikan permasalahan ini digunakan bantuan program Visual Basic 6.0 untuk menghasilkan suatu lintasan terpendek dari tiga pintu masuk yang ada di Kabupaten dan Kota Probolinggo yaitu Pasuruan, Lumajang, dan Situbondo menuju tempat-tempat wisata yang ada di Kabupaten dan Kota Probolinggo. Data yang digunakan berupa tempat-tempat wisata dan persimpangan jalan yang ada di Kabupaten dan Kota Probolinggo. Hasil dari penyelesaian permasalahan dengan algoritma Bellman-Ford adalah tempat wisata yang paling dekat dari pintu masuk Kabupaten dan Kota Probolinggo dari arah Pasuruan yang berawal di Persimpangan Polsek Tongas adalah Air Terjun Madakaripura sebesar ± 12,3 Km. Tempat wisata yang paling dekat dari pintu masuk Kabupaten dan Kota Probolinggo dari arah Lumajang yang berawal Pertigaan Pos Polisi Leces adalah Danau Ronggojalu sebesar ± 3 Km. Tempat wisata yang paling dekat dari pintu masuk Kabupaten dan Kota Probolinggo dari arah Situbondo yang berawal Pertigaan Paiton adalah Candi Jabung ± 7 Km.