PENERAPAN ALGORITMA DIJKSTRA DAN FLOYD-WARSHALL UNTUK MENENTUKAN RUTE TERPENDEK TEMPAT WISATA DI BATANG

  • Leni Marlina UNNES
  • Amin Suyitno Universitas Negeri Semarang
  • Mashuri Mashuri Universitas Negeri Semarang
Keywords: Dijkstra, Floyd-Warshall, Rute Terpendek

Abstract

Fasilitas petunjuk arah menuju tempat-tempat wisata di Batang sangat minim, sehingga para wisatawan kesulitan mencari rute yang efisien menuju tempat-tempat wisata tersebut. Permasalahannya adalah bagaimana menentukan rute terpendek tempat wisata di Batang menggunakan algoritma Dijkstra dan Floyd-Warshall. Tujuan penelitian ini adalah untuk menemukan penyelesaian dari penerapan algoritma Dijkstra dan Floyd-Warshall dalam menentukan rute terpendek dari stasiun/terminal di Batang menuju ke tempat wisata di Batang. Langkah-langkah dari penelitian meliputi (1) membuat graf berbobot rute tempat wisata di Batang, (2) menemukan penyelesaian dari penerapan algoritma Dijkstra, (3) menemukan penyelesaian dari penerapan algoritma Floyd-Warshall, (4) menentukan rute terpendek yang direkomendasikan. Berdasarkan hasil penelitian diperoleh 27 rute terpendek di mana 25 rute adalah sama dan terdapat 2 rute yang berbeda. Rute yang berbeda tersebut yaitu (1) rute terpendek dari Terminal Banyuputih ke Tubing Pandansari dan (2) rute terpendek dari Terminal Banyuputih ke Bandar Ecopark. Dapat disimpulkan bahwa algoritma Dijkstra lebih tepat untuk digunakan dalam menentukan rute terpendek tempat wisata di Batang.

References

Aini, A., & Salehipour, A. (2012). Speeding Up The Floyd-Warshall Algorithm for The Cycled Shortest Path Problem. Iran: Elsevier Ltd. Journal of Applied Mathematics Letters, 25(2012), 1-5. Doi:10.1016/j.aml.2011.06.008.
Bell, E. T. (1952). Mathematics: Queen and Servant of Science. London: G. Bell & Sons, Ltd.
Faro, A., & Giordano, D. (2016). Algorithm to Find Shortest and Alternative Path in Free Flow and Congested Traffic Regimes. Italy: Elsevier B.V. Journal of Electrical, Electrinics and Computer Engineering, 73(2016), 1-29. Doi:10.1016/j.trc.2016.09.009.
Galan-Garcia, J. L., Aguilera-Venegas, G., Galan-Garcia, M. A., & Rodriguez-Cielos, P. (2014). A New Probabilistic of Dijkstra’s Algorithm to Simulate More Realistic Traffict Flow in A Smart City. Spain: Elsevier Inc. Journal of Applied Mathematics and Computation, 30(2014), 86-96. Doi:10.1016/j.aml.2014.11.076.
Hougardy, S. (2010). The Floyd-Warshall Algorithm on Graph With Negative Cycles. Germany: Elsevier B. V. Journal of Information Processing Letters, 110(2010), 279-281. Doi:10.1016/j.ipl.2010.02.001.
Kreyszig, E. (1993). Matematika Teknik Lanjutan. Jakarta: Gramedia Pustaka Utama.
Mardlootillah, H. I., Suyitno, A., & Arini, F. Y. (2015). Simulasi Algoritma Dijkstra dalam Menangani Masalah Lintasan Terpendek pada Graf Menggunakan Visual Basic. Indonesia: UNNES. Journal of Mathematics, 4(2) (2015). [http://journal.unnes.ac.id/sju/index.php/ujm/article/view/9349]
Munir, R. (2010). Matematika Diskrit. Bandung: Informatika.
Novandi, R. A. (2007). Perbandingan Algoritma Dijkstra dan Algoritma Floyd-Warshall dalam Penentuan Rute Terpendek (Single Pair Shortest Path). Institut Teknologi Bandung. Bandung.
Pandey, H. M. (2008). Design Analysis and Algoritms. University Science Press New Delhi. India.
Peyer, S., Rautenbach, D., & Vygen, J. (2009). A Generalization of Dijkstra’s Shortest Path Algorithm Applications to VLSI routing. Germany: Elsevier B.V. Journal of Discrete Algorithm, 7(2009), 377-390. Doi:10.1016/j.jda.2007.08.003.
Published
2017-10-20
Section
Articles