Implementasi Algoritma Bellman-Ford untuk Pencarian Jalur Terpendek Menuju Rumah Sakit di Kota Yogya Berbasis Android

Authors

  • Rendy Setiawan Universitas Kristen Duta Wacana
  • R. Gunawan Santosa Universitas Kristen Duta Wacana
  • Junius Karel Tampubolon Universitas Kristen Duta Wacana

DOI:

https://doi.org/10.21460/jutei.2019.32.184

Abstract

Kota Yogyakarta merupakan Kota Pelajar dan Kota Wisata. Banyak wisatawan maupun pelajar yang datang ke Kota Yogyakarta untuk belajar dan berlibur. Tetapi banyak dari pendatang tersebut yang tidak tahu mengenai lokasi dari rumah sakit di Kota Yogyakarta. Penelitian ini akan mencoba membuat aplikasi pencarian jalur terpendek menuju rumah sakit menggunakan algoritma Bellman-Ford berbasis Android. Algoritma Bellman-Ford merupakan salah satu algoritma untuk pencarian jalur terpendek. Dalam prosesnya, penulis mengambil data berupa koordinat jalan dan koordinat rumah sakit, lalu membuatnya menjadi satu kesatuan graf. Setelah mendapatkan graf, penulis menggunakan algoritma Bellman-Ford untuk mencari jalur terpendek.  Hasil pencarian jalur terpendek akan dibandingkan dengan hasil pencarian dari Google Maps. Pengujian pencarian jalur terpendek dilakukan sebanyak 20 kali dan berhasil dilakukan dan menunjukan bahwa algoritma Bellman-Ford mampu memberikan jalur terpendek yang sama sebesar 80% dengan Google Maps, bahkan rata-rata jarak yang dikeluarkan lebih baik sebanyak 30.2m dibanding dengan rata-rata jarak yang dikeluarkan Google Maps. Pengujian ini juga menemukan bahwa semakin banyak jumlah verteks dan edge dalam data akan mempengaruhi lama proses algoritma untuk mencari jalur terpendek karena algoritma Bellman-Ford harus mengecek setiap verteks dan edge.

References

Christian, A. (2013). Studi Literatur Perbandingan Algoritma Dijkstra dan Bellman-Ford dalam Pencarian Jarak Terdekat. Undergraduate Thesis, Duta Wacana Christian University.

Kristyaningrum, I. (2009). Perbandingan Algoritma Dijkstra dan Bellmanford Untuk Pencarian Jalur Terpendek Pada Graf Berarah. Undergraduate thesis, Duta Wacana Christian University.

Kurniawijaya, P. A. (2010). Pencarian Pom Bensin Terdekat di Denpasar Menggunakan Algoritma Dijktsra. Undergraduate thesis, Duta Wacana Christian University.

Halim, J. (1998). Visualisasi Jalur Terpendek dengan Algoritma Bellman-Ford Pada Studi Kasus Jalan Darat Antar Kota (Pulau Jawa). Undergraduate Thesis, Duta Wacana Christian University.

Munir, R. (2010). Matematika Diskrit. Bandung: Penerbit Informatika Bandung.

Safaat, N. (2012). Pemrograman Aplikasi Mobile Smartphone Dan Tablet Pc Berbasis Android. Bandung: Informatika Bandung.

Susilo, Y. S., Pranjoto, H., & Gunadhi, A. (2014). Sistem Pelacakan dan Pengamanan Kendaraan Berbasis GPS dengan Menggunakan Komunikasi GPRS. Jurnal Ilmiah Widya Teknik, 22.

Hudiono, Taufik, M., Koesmarijanto, & Darmono, H. (2018). Sistem Komunikasi Radio dan Laboratorium. Polinema.

Tulach, J. (2008). Practical API Design: Confessions of a Java Framework Architect. Apress.

Svennerberg, G. (2010). Beginning Google Maps API 3. Apress.

Cormen, T. H. (2009). Introduction to Algorithms (Vol. III). Cambridge: The MIT Press.

Published

2021-07-13

How to Cite

[1]
R. . Setiawan, R. G. Santosa, and J. K. Tampubolon, “Implementasi Algoritma Bellman-Ford untuk Pencarian Jalur Terpendek Menuju Rumah Sakit di Kota Yogya Berbasis Android”, JUTEI, vol. 3, no. 2, pp. 95–104, Jul. 2021.