Journal of Information System, Applied, Management, Accounting and Research. http://journal.stmikjayakarta.ac.id/index.php/jisamar , jisamar@stmikjayakarta.ac.id , jisamar2017@gmail.com e-ISSN: 2598-8719 (Online), p-ISSN: 2598-8700 ( Printed) , Vol. 6 No.1,   Februari 2022

## IMPLEMENTASI ALGORITMA DIJKSTRA DALAM PENENTUAN RUTE TERDEKAT MENUJU MASJID DI PERUMAHAN BONA INDAH LEBAK BULUS
Achmad Fatkharrofiqi 1*, Windu Gata 2
Program Studi Ilmu Komputer Fakultas Teknologi Informasi Universitas Nusa Mandiri 14002469@nusamandiri.ac.id , windu@nusamandiri.ac.id
Received: December 30, 2021 . Revised: January 5, 2022 . Accepted: January 7, 2022 . Issue Period: Vol.6 No.1 (2022), Page 87-92
Abstrak: Penerapan  kecerdasan  buatan  ( Artificial  Intelligence )  untuk  pemecahan  masalah ( problem  solving )  dalam  bidang  ilmu  komputer  telah  mengalami  perkembangan  yang  pesat dari tahun ke tahun  seiring perkembangan  kecerdasan buatan itu  sendiri. Permasalahan  yang melibatkan  pencarian  ( searching )  adalah  salah  satu  contoh  penggunaan  kecerdasan  buatan yang  cukup  popular  untuk  memecahkan  berbagai  macam  permasalahan.  Dalam  aktifitas sehari-hari,  penggunaan  jalan  selalu  menjadi  aktifitas  yang  tidak  dapat  dihindari,  sehingga penentuan  lintasan  terpendek  dari  satu  titik  ke  titik  yang  lain  menjadi  masalah  yang  sering ditemui. Hal ini pula dirasakan oleh warga yang tinggal dalam sebuah perumahan yang cukup luas.  Terkadang  untuk  dapat  mencapai  tempat  yang  dituju  sering  kali  bingung  dalam menentukan  jalan  mana  yang  harus  dilalui  untuk  mendapatkan  jarak  terpendek  sampai  ke tujuan.  Perumahan  Bona  Indah  merupakan  kawasan  perumahan  di  wilayah  Kecamatan Cilandak, Kota Jakarta Selatan, di dalam perumahan terdapat sebuah masjid yang berlokasi di sisi  pojok  selatan  perumahan  Bona  Indah.  Banyaknya  jumlah  blok  menimbulkan permasalahan mengenai rute terpendek yang dapat ditempuh oleh warga untuk menuju masjid. Maka,  tujuan  penelitian  ini  adalah  untuk  menentukan  jalur  terpendek  yang  ditempuh  warga untuk  sampai  ke  masjid.  Metode  yang  digunakan  adalah  dengan  menerapkan  Algoritma Djikstra yang mampu menghasilkan rute terpendek bagi warga untuk menuju ke masjid.
Kata kunci: Algoritma Dijkstra; Rute Terpendek; Pencarian
Abstract: The  application  of  artificial  intelligence  (Artificial  Intelligence)  to  solve  problems (problem  solving)  in  the  field  of  computer  science  has  experienced  rapid  development  from year  to  year  along  with  the  development  of  artificial  intelligence  itself.  Problems  involving searching are one example of the use of artificial intelligence which is quite popular to solve various kinds of problems. In daily activities, road use is always an unavoidable activity, thus making the shortest path from one point to another a problem that is often encountered. This is  felt  by  residents  who  live  in  a  large  housing  estate.  sometimes  to  reach  the  destination  is often confused in determining which way to go to get the shortest distance to the destination. Bona Indah Housing is a residential area in the Cilandak District, South Jakarta City, inside the housing there is a mosque which is located on the south side of the Bona Indah housing complex. The large number of blocks causes problems regarding the shortest route that can be taken  by  residents  to  get  to  the  mosque.  So,  the  purpose  of  this  study  was  to  determine  the shortest path taken by residents to get to the mosque. The method used is to apply the Djikstra Algorithm which can produce the shortest route for residents to go to the mosque.
Keywords: Djikstra Algorithm; Shortest Route; Search
Journal of Information System, Applied, Management, Accounting and Research. http://journal.stmikjayakarta.ac.id/index.php/jisamar , jisamar@stmikjayakarta.ac.id , jisamar2017@gmail.com e-ISSN: 2598-8719 (Online), p-ISSN: 2598-8700 ( Printed) , Vol. 6 No.1,   Februari 2022

## I. PENDAHULUAN
Penerapan Artificial  Intelligence pada  pemecahan  masalah  di  bidang  ilmu  komputer  mengalami perkembangan  yang  pesat  dari  tahun  ke  tahun  seiring  dengan  perkembangan  kecerdasan  buatan  itu  sendiri. Permasalahan pencarian merupakan salah satu contoh penggunaan kecerdasan buatan yang cukup populer untuk menyelesaikan berbagai masalah. Aplikasinya bermacam-macam, mulai dari permasalahan dunia nyata, seperti penentuan rute di peta, travelling salesman problem (TSP), penentuan urutan perakitan ( assembly sequencing ) oleh  robot,  hingga  aplikasi  di  dunia game ,  seperti  komputer  mampu  memainkan  catur  seperti  manusia  atau menentukan  untuk  mengambil  jalur  karakter  dalam  sebuah  permainan  [1].  Dalam  aktivitas  sehari-hari, penggunaan jalan selalu menjadi aktivitas yang tidak bisa dihindari. Dalam proses perpindahan dari lokasi awal ke  lokasi  tujuan,  melewati  beberapa  jalan  raya.  Jalan  merupakan  sarana  transportasi  yang  setiap  rutenya merupakan  jaringan  yang  kompleks  [2].  Dalam  teori  graf,  Menentukan  jalur  optimal  dari  satu  titik  ke  titik lainnya merupakan masalah yang sering dijumpai dalam kehidupan sehari-hari [3]. Hal ini juga dirasakan oleh penghuni  yang  tinggal  di  perumahan  yang  cukup  luas.  Terkadang  untuk  sampai  ke  tujuan  dengan  cepat  maka jarak terpendek dari lokasi awal harus ditemukan  untuk sampai  ke tujuan  yang diinginkan tanpa  melalui jalan raya sebanyak 2 (dua) kali [4].
Perumahan  Bona  Indah  merupakan  kawasan  hunian  di  kawasan  Kecamatan  Cilandak,  Kota  Jakarta Selatan.  Di  dalam  perumahan  Bona  Indaht  terdapat  sebuah  masjid  yang  terletak  di  sudut  selatan  perumahan Bona Indah atau di ujung tenggara Jalan Bona Indah IV. Jumlah blok yang banyak menimbulkan permasalahan terkait  rute  terpendek  yang  bisa  ditempuh  warga  untuk  menuju  masjid.  Masalah  menemukan  jalur  terpendek dalam suatu grafik merupakan salah satu masalah optimasi [5]. Dalam mencari jalur terpendek, semakin banyak titik  dan  garis  pada  sebuah  grafik,  semakin  rumit  dan  memakan  waktu  [6]  saat  melakukan  pencarian  secara manual.  Oleh  karena  itu,  diperlukan  program  pendukung  untuk  mencari  jalur  terpendek  pada  grafik  untuk mempercepat  pencarian.  Program  yang  dirancang  merupakan  simulasi  pencarian  jalur  terpendek  pada  sebuah grafik. Simulasi tersebut dirancang untuk memberikan kemudahan dan menghindari kesalahan perhitungan bagi masyarakat awam yang ingin menerapkan pencarian jalur terpendek dalam kehidupan sehari-hari.
Salah satu metode algoritma yang digunakan dalam pencarian jarak terpendek adalah algoritma Dijkstra. Algoritma Dijkstra merupakan algoritma yang paling sering digunakan dalam pencarian rute terpendek, mudah digunakan  dengan  menggunakan  node  sederhana  pada  jaringan  jalan  yang  tidak  rumit  [7].  Prinsip  algoritma Dijkstra adalah mencari dua jalur terkecil. Algoritma Dijkstra memiliki iterasi untuk mencari titik yang jaraknya dari titik awal paling pendek  [8]. Algoritma Dijkstra dinamai menurut penemunya, Edsger Dijkstra. Algoritma Dijkstra  menggunakan  prinsip greedy ,  dimana  pada  setiap  langkah  sisi  dengan  bobot  minimum  yang  dipilih menghubungkan node yang dipilih ke node lain yang tidak dipilih [9].
Input  dari  algoritma  ini  adalah  graf  berarah  dan  berbobot,  G  dan  simpul  sumber  s  pada  G.V  adalah himpunan  dari  semua  simpul  pada  graf  G.  Setiap  sisi  graf  ini  merupakan  sepasang  simpul  (u,  v)  yang melambangkan hubungan dari simpul u ke simpul v. Himpunan semua sisi yang disebut E. Bobot dari sisi-sisi dihitung dengan fungsi w: E → [0, ∞]; jadi w (u, v) adalah jarak non-negatif dari simpul u ke simpul v. Biaya sebuah sisi dapat dianggap sebagai jarak antara dua simpul, yang merupakan penjumlahan dari jarak semua sisi pada  jalur.  Untuk  sepasang  simpul  s  dan  t  pada  V,  algoritma  ini  menghitung  jarak  terpendek  dari  s  ke  t  [9]. Algoritma  Dijkstra  telah  banyak  digunakan  dalam  penelitian  untuk  menyelesaikan  masalah  jalur  terpendek, diantaranya  Sodik  Kirono,  et.  al.,  menggunakan  model  grafik  dan  algoritma  Dijkstra  dalam  menentukan  rute kendaraan di jalan tol [10].
Bilqis Amaliyah  menggunakan kombinasi node berdasarkan algoritma Dijkstra untuk  menentukan jarak terpendek  antar  kota  di  Pulau  Jawa  [11].  Antonio  Gusmau,  et.  al.,  menggunakan  algoritma  Djikstra  dalam merancang Sistem Informasi Geografis Pariwisata Berbasis Web untuk pencarian jalur terpendek di Timor Leste dengan  akurasi  nilai  jarak  rata-rata  0,03%  pengukuran  dengan Google  Earth [12].  Berdasarkan  studi  yang dilakukan  oleh  peneliti  sebelumnya,  penggunaan  algoritma  Djikstra  merupakan  pilihan  yang  tepat  dalam menyelesaikan permasalahan dalam menentukan rute terpendek menuju masjid di perumahan Bona Indah.

## II. METODE DAN MATERI
Journal of Information System, Applied, Management, Accounting and Research. http://journal.stmikjayakarta.ac.id/index.php/jisamar , jisamar@stmikjayakarta.ac.id , jisamar2017@gmail.com e-ISSN: 2598-8719 (Online), p-ISSN: 2598-8700 ( Printed) , Vol. 6 No.1,   Februari 2022
Pada penelitian ini penulis menggunakan data citra Bona Indah dari Google Map sebagai peta dasar dan identifikasi  kode blok. Kemudian, pada setiap titik potong  diberi label sebagai node (V1, V2, V3... Vn). Jalur yang  menghubungkan node diidentifikasi  sebagai edge .  Ukuran  setiap  tepi  dihitung  menggunakan Google Maps .
Sumber: (Google Maps) Gambar 1. Peta Bona Indah
Proses  penentuan  jarak  terpendek  dengan  algoritma  Dijkstra  pada  penelitian  ini  dapat  diilustrasikan dengan diagram berikut:
Sumber: [13] Gambar 2. Langkah-langkah Penelitian
Tahapan  percobaan  yang  dilakukan  penulis  dalam  melakukan  penelitian  ini  ditempuh  dalam  beberapa langkah di bawah ini [13]:
1. Tentukan Peta Dasar
Langkah pertama adalah menentukan peta dasar sebagai bahan penelitian.
2. Tentukan Node dan Label
Langkah  kedua  adalah  menetapkan node dan  memberi  label  pada  setiap node .  Berdasarkan  peta dasar yang telah ditentukan, yang dianggap sebagai simpul adalah setiap persimpangan perumahan, dan diberi label pada setiap simpul.
3. Mengukur Jarak antar Node Proses selanjutnya adalah mengukur jarak antar node , dengan langkah-langkah sebagai berikut:
a. Atur jarak semua node sebagai “ infinite ”, kemudian atur jarak node awal (sumber) ke nilai 0.
b. Tandai  jarak node awal  sebagai  nilai  permanen,  sedangkan  jarak node lainnya  sebagai  a  nilai sementara.
c. Menetapkan simpul awal sebagai simpul aktif.
d. Menghitung  jarak  temporer  semua  simpul  yang  bertetangga  dengan  simpul  aktif  dengan menjumlahkannya dengan panjang edge .
Journal of Information System, Applied, Management, Accounting and Research. http://journal.stmikjayakarta.ac.id/index.php/jisamar , jisamar@stmikjayakarta.ac.id , jisamar2017@gmail.com e-ISSN: 2598-8719 (Online), p-ISSN: 2598-8700 ( Printed) , Vol. 6 No.1,   Februari 2022
e. Jika  hasil  perhitungan  jarak  lebih  kecil  daripada  nilai  sementara,  pembaruan  nilai  jarak  pada simpul itu dilakukan.
f. Tetapkan node dengan nilai jarak temporer terkecil sebagai node aktif dan tandai nilai jarak pada node tersebut sebagai nilai permanen.
g. Ulangi langkah 4 sampai 7 hingga tidak ada lagi node dengan nilai permanen yang bertetangga dengan nilai jarak temporer.
4. Analisi Hasil
Setelah  semua  proses  telah  dilakukan,  langkah  terakhir  adalah  menganalisis  hasil  pengujian pengukuran  rute  terpendek  menggunakan  algoritma  Djikstra,  dan  menarik  kesimpulan  dari  hasil analisis tersebut.

## III. PEMBAHASA DAN HASIL
3.1 Proses Identifikasi Node / Vertex Berdasarkan peta perumahan Bona Indah yang diperoleh, sebuah node ditentukan dan diberi label untuk setiap node . Dari proses identifikasi diperoleh 12 node .
Gambar 3. Identifikasi Node / Vertex

## 3.2 Proses Pengukuran Jarak Antar Node
Pengukuran jarak ke setiap node dilakukan dengan menggunakan Google Maps sehingga diperoleh data dari jarak node sebagai berikut:
Table I. Data Jarak Antar Node Node Jarak (Meter) a b V1 V2 70 V2 V3 58 V2 V11 170 V3 V4 57 V3 V9 210 V4 V5 58 V4 V8 150 V5 V6 110 V5 V7 87 V6 V7 99 V7 V8 52 V8 V9 52 V9 V10 56 V11 V10 81
Journal of Information System, Applied, Management, Accounting and Research. http://journal.stmikjayakarta.ac.id/index.php/jisamar , jisamar@stmikjayakarta.ac.id , jisamar2017@gmail.com e-ISSN: 2598-8719 (Online), p-ISSN: 2598-8700 ( Printed) , Vol. 6 No.1,   Februari 2022
Jadi, rute terpendek dari hasil pengujian dari node V1 sampai V10 yaitu V1-V2-V11-V10 dengan jarak 321 meter.

## IV. KESIMPULAN
Berdasarkan  metodologi  dan  pengujian  yang  telah  dilakukan  maka  dapat  disimpulkan  bahwa  algoritma Dijkstra dapat membantu warga perumahan Bona Indah untuk menentukan rute terdekat menuju masjid. Hasil penelitian ini tetap dapat dikembangkan dengan menambah perkiraan waktu tempuh yang dibutuhkan sehingga dapat  memberikan  saran  kepada  warga  untuk  berangkat  ke  masjid  agar  dapat  sampai  di  masjid  tepat  waktu shalat.

## REFERENASI
[1] Budihartono, “Penerapan Algoritma Dijkstra untuk Sistem Pendukung Keputusan bagi Penentuan Jalur Terpendek Pengirmiman Paket Barang pada Travel,” Senit , 2016.
[2] Moch. H. H. Ichsan, E. Yudaningtyas, and M. A. Muslim, “Solusi Optimal Pencarian Jalur Tercepat dengan Algoritma Hybrid Fuzzy-Dijkstra,” Jurnal EECCIS , vol. 6, p. 2, 2021.
[3] U. Rifanti, “Pemilihan Rute Terbaik Menggunakan Algoritma Dijkstra Untuk Mengurangi Kemacetan Lalu Lintas di Purwokerto,” JMPM: Jurnal Matematika dan Pendidikan Matematika , vol. 2, p. 90, Dec. 2017, doi: 10.26594/jmpm.v2i2.926.
[4] M. Harahap and N. Khairina, “Pencarian Jalur Terpendek dengan Algoritma Dijkstra,” SinkrOn , vol. 2, p. 18, Dec. 2017, doi: 10.33395/sinkron.v2i2.61.
[5] H. Ilmi Mardlootillah, A. Suyitno, and F. Yuni Arini, “SIMULASI ALGORITMA DIJKSTRA DALAM MENANGANI MASALAH LINTASAN TERPENDEK PADA GRAF MENGGUNAKAN VISUAL BASIC,” UJM , vol. 3, no. 1, 2014, [Online]. Available: http://journal.unnes.ac.id/sju/index.php/ujm
[6] N. Nggufron and M. Rochmad, “PENCARIAN RUTE TERBAIK PEMADAM KEBAKARAN KOTA SEMARANG MENGGUNAKAN ALGORITMA DIJKSTRA DENGAN LOGIKA FUZZY SEBAGAI PENENTU BOBOT PADA GRAF,” 2019. [Online]. Available: http://journal.unnes.ac.id/sju/index.php/ujm
[7] Y. Primadasa, “PENCARIAN RUTE TERPENDEK MENGGUNAKAN  ALGORITMA DIJKSTRA PADA SIG BERBASIS WEB UNTUK  DISTRIBUSI MINUMAN  (STUDI KASUS PT.COCA-COLA KOTA PADANG),” Jurnal KomTekInfo Fakultas Ilmu Komputer , vol. 2, p. 2, 2015.
[8] D. Ardana and R. Saputra, Penerapan Algoritma Dijkstra pada Aplikasi Pencarian Rute Bus Trans Semarang . 2016.
[9] D. O. Pugas, M. Somantri, and K. I. Satoto, “Pencarian Rute Terpendek Menggunakan Algoritma Dijkstra dan Astar (A*) pada SIG Berbasis Web untuk Pemetaan Pariwisata Kota Sawahlunto,” Transmisi: Jurnal Ilmiah Teknik Elektro , vol. 13, no. 1, pp. 27–32, 2011, doi: 10.12777/TRANSMISI.13.1.27-32.
[10] S. Kirono, M. I. Arifianto, R. E. Putra, A. Musoleh, and R. Setiadi, “Graph-based modeling and dijkstra algorithm for searching vehicle routes on highways,” International Journal of Mechanical Engineering and Technology , vol. 9, pp. 1273–1280, Dec. 2018.
Journal of Information System, Applied, Management, Accounting and Research. http://journal.stmikjayakarta.ac.id/index.php/jisamar , jisamar@stmikjayakarta.ac.id , jisamar2017@gmail.com e-ISSN: 2598-8719 (Online), p-ISSN: 2598-8700 ( Printed) , Vol. 6 No.1,   Februari 2022
[11] B. Amaliah, C. Fatichah, and O. Riptianingdyah, “Finding the shortest paths among cities in Java Island using node combination based on Dijkstra algorithm,” International Journal on Smart Sensing and Intelligent Systems , vol. 9, pp. 2219–2236, Dec. 2016, doi: 10.21307/ijssis-2017-961.
[12] A. Gusmão, S. H. Pramono, and Sunaryo, “Sistem Informasi Geografis Pariwisata Berbasis Web Dan Pencarian Jalur Terpendek Dengan Algoritma Dijkstra,” Jurnal EECCIS , vol. 7, p. 2, 2013.
[13] S. Lestari, A. Ardiansyah, A. Giovani, and D. Dwijayanti, “A DIJKSTRA ALGORITHM IMPLEMENTATION IN DETERMINING SHORTEST ROUTE TO MOSQUE IN RESIDENTIAL CITRA INDAH CITY,” Pilar Nusa Mandiri: Journal of Computing and Information System , vol. 16, no. 1, pp. 65–70, Mar. 2020, doi: 10.33480/pilar.v16i1.1199.