## Implementasi Algoritma Bellman Ford Pada Aplikasi Pencarian Pengobatan Patah Tulang Kem Kem Terdekat di Kota Medan
Berbasis Android

## Surya Wijaya
Program Studi Teknik Informatika, STMIK Budi Darma, Medan, Indonesia Jalan Sisingamangaraja No. 338 Medan, Indonesia

## Abstrak
Pencarian jarak terpendek merupakan suatu permasalahan bagi orang yang sedang mengalami patah tulang atau terkilir, karna dalam keadaan darurat sepertini akan timbul kepanikan yang besar sehingga sering kali korban akan mengalami hal yang fatal karna  keterlambatan  dalam  melakukan  penanganan,  sehingga  tak  jarang  keluarga  korban  mencari  jalur  terpendek  untuk mencapai  penanganan  pertama  tersebut,  seperti  pengobatan  patah  tulang  kem  kem  adalah  salah  satu  contoh  penanganan pertama  dalam  melakukan  pengobatan  patah  tulang,  efesiensi  waktu  dan  biaya  sangat  di  butuhkan  dalam  keadaan  darurat seperti ini, sehingga dapat  meminimalkan  hal  hal fatal  yang akan terjadi pada  korban patah tulang. Salah satu  cara paling efektif  dalam  keadaan  darurat  seperti  ini  dengan  melakukan  pencarian  rute  alternatif  paling  cepat  untuk  bisa  sampai  di pengobatan patah tulang kem kem. Aplikasi pencarian jarak terpendek  yang di buat, di dasarkan pada metode bellman ford. Metode bellman ford adalah sebuah algoritma yang menghitung jalur terpendek dari sumber titik tunggal untuk mencari simpul lain. Hasil dari penelitian ini agar mampu menemukan titiik terdekat pengobatan patah tulang kem kem untuk meminimalakan hal hal fatal yang terjadi pada korban, sehinggga korban dapat segera di tangani dan mendapatka perawatan.
Kata Kunci : Lintasan Terpendek, Kem Kem, Bellman Ford.

## Abstract
Searching  for  the  shortest  distance  is  a  problem  for  people  who  are  experiencing  fractures  or  dislocations,  because  in  an emergency like this there will be a big panic that often victims will experience fatal things due to delays in handling, so often the victim's family looks for the shortest path to achieving the first treatment, such as the treatment of kem fractures is one of the first examples of treatment in the treatment of fractures, the efficiency of time and cost is needed in an emergency like this, so as to minimize the fatal things that will happen to victims of fractures. One of the most effective ways in an emergency like this is to search for the fastest alternative route to get to the treatment of Kem fractures. The shortest distance search application made, based on the Bellman Ford method. The bellman ford method is an algorithm that calculates the shortest path from a single point source to find another node. The results of this study are to be able to find the closest point of treatment for  Kem fracture to minimize fatalities that occur to the victim, so that the victim can be treated immediately and get treatment.
Keywords : Shortest Track, Kem Kem, Bellman Ford.

## 1. PENDAHULUAN
Pencarian  merupakan suatu kegiatan dalam  melakukan penjelajahan dengan tujuan untuk menemukan sesuatu, seperti  daerah  yang  tidak  dikenal,  mencari  barang,  tempat,  dan  sebagainya,  dengan  rentan  waktu  secepatnya. Dalam ilmu komputer pencarian merupakan kegiatan untuk mendapatkan sesuatu bentuk informasi yang terdapat didalam berkas. Lintasan terpendek didalam graf merupakan salah satu persoalan optimasi. Graf yang digunakan dalam pencarian adalah graf berbobot (Weighted graph), yaitu graf yang setiap sisinya diberikan suatu nilai atau bobot. Bobot pada sisi graf dapat menyatakan jarak antar kota, waktu pengirimaan pesan, ongkos pembangunan, dan sebagainya.
Pengobatan patah tulang kem kem merupakan salah satu jasa pelayanan khusus dalam menangani patah tulang, ataupun tulang terkilir. Saat ini pengobatan patah tulang kem kem sangat jarang di temui, karna dianggap masih terlalu tradisional dimata masyarakat, padahal  dalam keadaan darurat pengobatan patah tulang kem kem juga  sangat  membantu  untuk  mengurangi  cidera  fatal  yang  terjadi  apabila  ada  korban  yang  mengalami  patah tulang. Dalam kegitannya Pengobatan patah tulang kem kem ini memiliki prinsip kerja yang hampir sama dengan cara kedokteran lakukan, dengan mengobati, merawat pasien, lalu mengurut posisi tulang yang patah ke posisi semula  atau  di  sebut  dengan  (reposisi),  setelah  posisi  tulang  diurut  dan  sudah  kembali  seperti  semula,  lalu mempertahankan  posisi  tulang  tersebut  sampai  proses  penyembuhan  patah  tulang  (immobilisasi),  agar  tulang tersebut dapat tersambung dengan posisi yang benar.
Pengobatan patah tulang kem kem ini akan menjadi salah satu pilihan alternatif bagi masyarakat apabila suatu  kejadian  darurat  ketika  cidera  tulang  terjadi,  dan  masalah  yang  sering  terjadi  pada  masyarakat  adalah kebingungan  akan  letak  pengobatan  patah  tulang  kem  kem  terdekat  dari  titik  kecelakaan  korban  tersebut. Kepanikan akan menambah bingungnya rute mana yang akan dilewati untuk segera sampai kepengobatan patah tulang kem kem, dan tak jarang sering terpilihnya rute terjauh, atau pengobatan patah tulang kem kem terjauh yang  didatangi,  sehingga  memungkinkan  resiko  hal  fatal  terjadi  lebih  besar  pada  korban,  karna  minimnya informasi tentang letak pengobatan patah tulang kem kem terdekat.
Implementasi pararel untuk memecahkan masalah jalur terpendek menggunakan algoritma Bellman Ford [1].  Algoritma  Bellman  Ford  dan  algoritma  Djikstra  untuk  menemukan  jalur  terkecil  dalam  aplikasi  GIS  [2].
M [I,y]= min [ M (y), ( M (i,s)  + EdgeWeight)
Implentasi pararel untuk memecahkan jalur masalah jalur terpendek menggunakan algoritma Bellman Ford [3]. Algoritma Bellman Ford Shortest Path mengggunakan Global Positoning System [4]. Penerapan Metode Bellman Ford Dalam Aplikasi Pencarian Lokasi Perseroan Terbatas di PT. Jakarta Industrial Estate Pulogadunng (PT.JIEP) [5]. Optimasi Jalur Tercepat Dengan Menggunakan Modifikasi Algoritma Bellman Ford [6].
Algoritma Bellman-Ford ditemukan oleh Richard E. Bellman, seorang matematikawan yang lahir di New York pada tahun 1920,  meninggal pada tanggal 19 maret 1984 dan Ford. Algoritma Bellman  Ford merupakan algoritma untuk mencari jarak terpendek (dari satu sumber) pada sebuah di graf berbobot, menggunakan relaksasi untuk menemukan jalur terpendek sumber tunggal pada grafik terarah, algoritma ini juga akan mendeteksi jika ada siklus berat negatif (sehingga tidak ada solusi). Algoritma  Djikstra dapat lebih cepat mencari hal yang sama dengan syarat tidak ada sisi (edge) yang berbobot negative. Algoritma Djikstra memang lebih cepat melakukan hal  yang  sama,  namun  Algoritma  Djikstra  hanya  berlaku  apabila  tidak  ada  sisi  yang  berbobot  negative. Maksudnya dari satu sumber ialah bahwa ia menghitung semua jarak terpendek yang berawal dari satu titik node. Algoritma Bellman-Ford menggunakan waktu sebesar O (V.E), di mana V dan E adalah banyaknya sisi dan titik. International journal of P2P Network and Tecnology (IJPTT)[1].

## 2. LANDASAN TEORI

## 2.1 Pencarian
Pencarian  merupakan suatu kegiatan dalam  melakukan penjelajahan dengan tujuan untuk menemukan sesuatu, seperti  daerah  yang  tidak  dikenal,  mencari  barang,  tempat,  dan  sebagainya,  dengan  rentan  waktu  secepatnya. Dalam ilmu komputer pencarian merupakan kegiatan untuk mendapatkan sesuatu bentuk informasi yang terdapat didalam berkas. Lintasan terpendek didalam graf merupakan salah satu persoalan optimasi. Graf yang digunakan dalam pencarian adalah graf berbobot ( Weighted graph), yaitu graf yang setiap sisinya diberikan suatu nilai atau bobot. Bobot pada sisi graf dapat menyatakan jarak antar kota, waktu pengirimaan pesan, ongkos pembangunan, dan sebagainya.

## 2.2  Metode Bellman Ford
Algoritma Bellman-Ford ditemukan oleh Richard E. Bellman, seorang matematikawan yang lahir di New York pada tahun 1920, meninggal pada tanggal 19 maret 1984 dan Ford. Algoritma Bellman Ford merupakan algoritma untuk mencari  jarak terpendek (dari satu sumber) pada sebuah di graf  berbobot, menggunakan relaksasi untuk menemukan jalur terpendek sumber tunggal pada grafik terarah, algoritma ini juga akan mendeteksi jika ada siklus berat negatif (sehingga tidak ada solusi). Algoritma  Djikstra dapat lebih cepat mencari  hal  yang sama dengan syarat tidak ada sisi (edge) yang berbobot negative. Algoritma Djikstra memang lebih cepat melakukan hal yang sama, namun Algoritma Djikstra hanya berlaku apabila tidak ada sisi yang berbobot negative. Maksudnya dari satu  sumber  ialah  bahwa  ia  menghitung  semua  jarak  terpendek  yang  berawal  dari  satu  titik  node. Algoritma Bellman-Ford menggunakan  waktu  sebesar  O  (V.E),  di  mana  V  dan  E  adalah  banyaknya  sisi  dan  titik . International journal of P2P Network and Tecnology (IJPTT) [1] . 1. Isi nilai pada bobot pada sebuah graf (rute) untuk setiap satu titik ke titik lainnya, nilai 0 di isikan pada node awal dan nilai tak terhingga terhadap node lain.
2. Isikan  nilai  pada  semua  node  yang  yang  belum  dilalui,  lalu  isi  nilai  pada node awal  sebagai  titik  node kejadian.
3. Perhitungan dilakukan dari node awal kejadian, lalu pertimbangkan node tetangga yang belum sama sekali dilalui dan hitung jaraknya dari titik keberangkatan. Contoh jika A ke B memiliki bobot jarak 8 dan dari B ke  node  C  berjarak  2,  maka  jarak  ke  C  melewati  B  menjadi  8+2=10.  Jika  jarak  ini  lebih  kecil  dari  jarak sebelumnya yang telah dilalui selanjutnya data lama  akan di hapus, kemudian simpan ulang  data jarak yang baru.
4. Ketika sudah selesai mempertimbangkan setiap jarak terhadap node tetangga, kemudian  tandai node yang telah dilalui. Node yang telah dilewati tidak akan pernah diperiksa ulang, jarak yang akan disimpan adalah jarak yang  memiliki nilai bobot rute terkecil yang akan menjadi solusi pencarian  jalur terpendek.
Formula Bellman Ford sebagai berikut:
..................................................................(1)
Keterangan: M : Marked
M(y) : Nilai dalam vertex awal ( node Y) M(i,s) : Nilai dalam vertex dari tujuan ( node i dan s) EdgeWeight  : Bobot dari sisi yang menghubungkan vertex .

## 2.3  Pengobatan patah tulang kem kem
Pengobatan patah tulang kem kem merupakan salah satu jasa pelayanan khusus dalam menangani patah tulang, ataupun tulang terkilir. Saat ini pengobatan patah tulang kem kem sangat jarang di temui, karna dianggap masih terlalu tradisional dimata  masyarakat, padahal  dalam keadaan darurat pengobatan patah tulang kem kem  juga sangat membantu untuk mengurangi cidera fatal yang terjadi apabila ada korban yang mengalami patah tulang. Dalam kegitannya Pengobatan patah tulang kem kem ini memiliki prinsip kerja yang hampir sama dengan cara kedokteran lakukan, dengan mengobati, merawat pasien, lalu mengurut posisi tulang yang patah ke posisi semula atau  di  sebut  dengan  ( reposisi ),  setelah  posisi  tulang  diurut  dan  sudah  kembali  seperti  semula,  lalu mempertahankan  posisi  tulang  tersebut  sampai  proses  penyembuhan  patah  tulang  ( immobilisasi ),  agar  tulang tersebut dapat tersambung dengan posisi yang benar .

## 3. ANALISA DAN PEMBAHASAN
Pada proses ini pengobatan patah tulang kem kem akan diberi tanda pada peta berupa titik titik, dan pada peta tersebut  akan  tampil  infromasi  mengenai  rute  terpendek  yang  dapat  di  lalui  dengan  secepatnya,  pada persimpangan jalan - jalan tersebut akan diberi titik - titik node untuk menentukan persimpangan mana yang akan dipilih. Permasalahan yang ada sebelumnya adalah rute yang akan dituju ke pengobatan patah tulang kem - kem tersebut  belum  di  ketahui  jalur  terpendeknya,  kemudian  juga  minimnya  informasi  lebih  lanjut  mengenai pengobatan patah tulang kem - kem dikota medan khusus nya didaerah Jermal Medan Denai. Menentukan node awal dan akhir.
Mulai =  Jl. Jermal I Medan Denai yang akan disimbolkan dengan variable (Y) Tujuan  =  Pengobatan  patah tulang  kem  kem  terdekat  dari  titik  lokasi  kejadian  yang  akan  disimbolkan  dengan variable (I) dan (S).
Gambar 1. Peta Lokasi Pencarian Pengobatan Patah Tulang Kem Kem
Keterangan Gambar peta di atas:
1. Setelah  dilakukan  riset  kelapangan  untuk  mendata  keberadaan  kem  kem  terdekat  guna  memenuhi  program aplikasi yang dibuat, maka ditemukanlah keberadaan kem kem terdekat dengan ditandainya titik node yang diberi simbol I dan S tersebut untuk menunjukan letak posisi kem kem berada.
2. Titik node yang diberi simbol huruf Y adalah keberadaan korban.
Setelah  dilakukan  penulisan  rutenya,  selanjutnya  menghitung  jarak  rute  yang  telah  dihitung  menjadi  kandidat, berikut adalah perhitunga jarak dari graf di atas: 1. 248 + 651 + 1,38 + 607 + 527 + 656 + 118 = 3,845 2. 248 + 651 + 1,38 + 1,32 + 142 + 126 + 116 = 3,353
3. 2,08 + 294 + 656 + 118 = 3,076
4. 2,08 + 639 + 305 + 118 = 3,070
5. 248 + 651 + 1,38 + 1,32 + 296 = 3,265
6. 2,08 + 639 + 305 + 613 + 260 + 129 + 127 + 139 = 4,220
7. 2,08 + 639 + 734 + 326 + 260 + 129 + 127 + 139 = 4,362
8. 248 + 651 + 1,38 + 1,32 + 142 + 122 + 139 + 94 + 139 = 3,605
9. 2,08 + 294 + 656 + 613 + 260 + 213 + 118 + 118 + 94 + 139 = 4,513
10. 2,08 + 639 + 305 + 613 + 260 + 213 + 138 + 118 = 4,294
Setelah di lakukan perhitungan dari graf yang menjadi kandidat, selanjutnya menggambarkan rute graf yang di lalui sebagai solusi kandidat satu persatu, berikut adalah gambaran graf nya.
1. Perhitungan rute =  Y – A – B – C – D – E – H – I
Gambar 2. Solusi Pencarian Rute – Langkah 1
Dari perhitungan Graf di atas dapatlah perhitungan langkah 1: 1. Y – A – B – C – D – E – H – I  = 248+651+1,38+607+527+656 118= 4,187
Berdasarkan  gambar  diatas  maka  dapatlah  kandidat  solusi  dari  permasalahan  pencarian  pengobatan  patah tulang kem kem terdekat dari titik kejadian yang berada diantara jalan jermal dua belas dan pasar empat belas Tembung, lalu rute di atas akan di bandingkan untuk mendapat jalur terpendeknya dengan formula Bellman Ford sebagai berikut:
Setelah dilakukan perhitungan  menggunakan rumus Bellman Ford satu satu persatu kandidat yang menjadi solusi jarak terpendek kepengobatan patah tulang kem  kem terdekat dari titik kejadian, lalu membuat tabel selanjutnya untuk mengelompokan kandidatnya kembali agar lebih mudah melihat hasil dari perhitungan jarak yang telah di hitung berikut tabel pengelompokannya:
Tabel 1. Daftar Rute Perjalanan Beserta Jaraknya No Rute Jarak (M) 1 Y – A – B – C – D – E – H – I 4,187 2 Y – A – B – C – L – K – J – I 3,353 3 Y – F – E – H – I 3,076 4 Y – F – G – H – I 3,070 5 Y – A – B – C – L – S 3,265 6 Y – F – G – H – W – V – U – T – S 4,220 7 Y – F – G – X – W – V – U – T – S 4,362 M [I,y]= min [ M (y), ( M (i,s)  + EdgeWeight)
8 Y – A – B – C – L – K – M – R – T – S 3,605 9 Y – F – E – H – W – V – P – Q – R – T – S 4,513 10 Y – F – G – H – W – V – P – O – I 4,294
Setelah dilakukan penguraian dan pengelompokan satu persatu dari graf diatas, maka solusi jarak terpendek yang dapat ditempuh kepengobatan patah tulang kem kem adalah: Y – F – G – H – I  = 2,08 + 639 + 305 + 118 = 3,070.

## 4.  IMPLEMENTASI
1. Form Menu Utama
Menu utama menampilkan pilihan yang tersedia pada aplikasi. Pada menu utama  tersedia tiga pilihan yaitu menu lokasi saya, About , dan Keluar, dimana tombol lokasi saya berisi link ke form lokasi dimana korban berada, tombol about berisi link ke form bantuan agar setiap user dapat menjalankan aplikasi dan tombol keluar berisi link untuk keluar dari aplikasi. Gambar untuk tampilan menu utama dapat dilihat pada gambar 3. dibawah ini:
Gambar 3. Activity Tampilan Menu utama 2. Form Lokasi Saya Form ini tampil ketika button lokasi saya di pilih, seperti terlihat pada gambar 4.2 dibawah ini:
Gambar 4. Activity Tampilan Lokasi Saya 3. Form Tampilkan Kem Kem Form ini tampil ketika button tampilkan bengkel dipilih dan berguna menampilkan pengobatan patah tulang kem  kem terdekat dari posisi dimana korban berada, dapat dilihat seperti gambar 4.3 dibawah ini:
Gambat 5. Activity Tampilan Jarak Terpendek
4. Form Detail Pengobatan patah Tulang Kem Kem Form ini tampil ketika button detail kem kem dipilih dan berguna menjelaskan secara detail data pengobatan patah tulang kem  kem dan jalur terpendek yang dilalui, dapat dilihat seperti gambar 4.4 dibawah ini:
Gambat 6. Activity Detail Pengobatan Patah Tulang Kem Kem

## 5. KESIMPULAN
Berdasarkan hasil penelitian yang telah dilakukan, maka dapat maka dapat diambil kesimpulan diantaranya:
1.  Hasil pengujian yang dilakukan proses pencarian rute terdekat sangat tergantung pada  data-data pengobatan paatah tulang kem kem yang diinputkan.
2.  Metode  Bellman  Ford  dapat  digunakan  untuk  menyelesaikan  permasalahan  pada  pencarian  rute  terpendek berbasis android.
3.  Dengan  Menggunakan  bahasa  pemograman  Java  dan  eclipse  sebagai  aplikasinya  dapat  membuat  aplikasi pencarian  rute  terpendek  berbasis  android  dan  memberikan  hasil  kepada  pengguna  lebih  mudah  dalam pencarian rute terpendek untuk mencari pengobatan patah tulang kem  kem terdekat.

## REFERENCES
[1]  FI.  Sigit  Suyantoro, Tuntunan  Praktis  Membangun  Sistem  Informasi  Akuntansi  Dengan  Visual  Basic  dan  Microsoft  SQL  Server , Rendrasta, Ed. Yogyakarta, indonesia: C.V ANDI OFFSET, 2007.
[2]  RINALDI  MUNIR, MATEMATIKA  DISKRIT ,  revisi  kelima  ed.,  RINALDI  MUNIR,  Ed.  Bandung,  indonesia:  INFORMATIKA Bandung, 2012.
[3]  Pankhari  Agarwal,  "New  Approach  of  Bellman  Ford  Algorithm  on  GPU  using  Compute  Unified  Design  Architecture  (CUDA)," International Journal of Computer Applications (0975 – 8887 , vol. 110, no. 13, p. 16, januari 2015.
[4]  Bhavana Mhatre 2, Amita Mehta 3. Sarala Khangare *1, "International Journal of Physiotherapy and Research," ASSOCIATION OF BONE MINERAL DENSITY AND BODY MASS , vol. 5, no. 2, p. 34, maret 2017.
[5]  Antonius Aditya  Hartanto, Mengenal  Aspek Teknis dan Bisnis Location  Based Service , pertama ed., Antonius Aditya  Hartanto, Ed. Jakarta, indonesia: Elex Media Komputindo, 2003.
[6]  Ali Zaki, Keliling Dunia Dengan Google Earth dan Google Maps , pertama  ed., Maria Agustina S, Ed. Yogyakarta, Indonesia: C.V ANDI OFFSET, 2010.
[7]  Eka Iswandy, "PERANCANGAN SISTEM INFORMASI TENTANG PENCATATAN HASIL TES," Jurnal TEKNOIF , vol. 2, no. 2, p. 6, Oktober 2014.
[8]  Sholiq, Pemodelan Sistem Informasi Berorientasi Objek dengan UML , pertama ed., Sholiq, Ed. Yogyakarta, indonesia: Graha Ilmu, 2006.
[9]  NAZRUDDIN  SAFAAT  H, ANDROID  PEMROGRAMAN  APLIKASI  MOBILE  SMARTPHONE  DAN  TABLET  PC  BERBASIS ANDROID , revisi kedua ed., NAZRUDDIN SAFAAT H, Ed. Bandung, indonesia: Informatika Bandung, 2015.
[10]  Ir. Yuniar Supardi, Pemrograman Database JAVA dan MySQL , pertama ed., Ir. Yuniar Supardi, Ed. Jakarta, Indonesia: PT Gramedia Jakarta, 2007.
[11]  AgustianAji  P  SholehHadi  Pramono  M.Aziz  Muslim,  "Parallel  Implementations  for  Solving  Shortest  Path  Problem  using  Bellman- Ford," International Journal of Computer Applications (0975 – 8887) , vol. Volume 95, no. Gaurav Hajela, p. 12, juni 2014.
[12]  Vaibhavi Patel, "A Survey Paper of Bellman-Ford Algorithm," International Journal of P2P Network Trends and Technology (IJPTT) , vol. Volume 5 , no. Assistant Professor, KalolInstitute of Technology & research Center, Gujarat, India, p. 23, February 2014.
[13]  Sarthak Budhiraja Rochan Mehrotra, "A Comparative Study between Bellman-Ford Algorithm and Dijkstras- Algorithms," Information Technology , vol. 1, no. 5, p. 22, mei 2014.
[14]  Mr. Abhishek Tyagi Ms. Kalpana, "Bellman Ford Shortest Path Algorithm using Global Positioning System," International Research Journal of Engineering and Technology (IRJET) , vol. Volume: 04 , no. 04, p. 12, april 2017.