## IMPLEMENTASI ALGORITMA DIJKSTRA UNTUK MENENTUKAN JALUR TERPENDEK  WILAYAH PISANGAN DAN KAMPUS NUSA MANDIRI TANGERANG
Astrid Noviriandini 1 , Maryanah Safitri 2
1 Program Studi Manajemen Ilmu Komputer STMIK Nusa Mandiri Jakarta http://www.nusamandiri.ac.id
astridnovi81@gmail.com 2 Program Studi Teknik Informatika STMIK Nusa Mandiri Jakarta http://www.nusamandiri.ac.id maryanahsafitri@gmail.com
Abstract— Congestion in Tangerang has become a daily  sight.  Many  steps  have  been  taken  by  the government  to  overcome  congestion.  However, congestion still happens. Therefore road users must find  their  own  way  to  solve  the  problem.  One effective way is to find the shortest alternative route that can be traversed by using Dijkstra Algorithm. The  use  of  Dijkstra's  Algorithm  can  provide  a solution  because  Dijkstra's  algorithm  gives  the output  of  the  fastest  and  shortest  path  from  the origin to the destination.
Intisari—Kemacetan  di  Tangerang  sudah menjadi  pemandangan  sehari-hari.  Banyak langkah-langkah  yang  sudah  dilakukan  oleh pemerintah  untuk  mengatasi  kemacetan.  Akan tetapi,  kemacetan  tetap  saja  masih  terjadi.  Oleh karena itu  pengguna jalan harus menemukan cara sendiri  untuk  mengatasi  masalah  tersebut.  Salah satu cara yang efektif  yaitu mencari rute alternatif terpendek yang dapat dilalui dengan menggunakan  Algoritma  Dijkstra.  Penggunaan Algoritma  Dijkstra  dapat  memberikan  solusi karena  Algoritma  Dijkstra  ini  memberikan keluaran berupa jalur tercepat dan terpendek dari tempat asal menuju tempat tujuan.
Kata  Kunci:  Algoritma  Dijkstra,  implementasi, Rute tercepat.

## PENDAHULUAN
Kemacetran  di  Kota  Tangerang  sudah menjadi  pemandangan  sehari-hari.  Berbagai langkah  sudah  ditempuh  oleh  pemerintah  untuk mengatasinya,  diantaranya  dengan  menerapkan Sistem  Kendali  Lalu  Lintas  Kendaraan  atau  Area Traffic  Control  System  (ATCS)  juga  memasang Traffic  Public  Announcement  (TPA)  di  sejumlah ruas jalan demi kelancaran lalu lintas (Warta Kota, 2017).  Namun  kemacetan  masih  saja  terjadi (Sanjaya,  Sulandari,  &  Basalim,  2016).  Untuk  itu,
pengguna jalan harus mencari solusi lain (Utama, Kuntjara,  &  Sutanto,  2016))  yaitu  dengan menentukan  jalan-jalan  manakah  yang  harus dilalui sehingga kita dapat mencari tempat tujuan dengan  jarak  terpendek  atau  mencari  jalur terdekat  (Wibowo  &  Wicaksono,  2012).  lintasan terpendek dapat diartikan sebagai bobot minimal dari  suatu  lintasan,  yaitu  jumlah  bobot  dari seluruh busur yang membentuk lintasan. Lintasan terpendek  dapat  ditentukan  dengan  beberapa algoritma  matematika,  salah  satunya  dengan Algoritma Dijkstra. Algoritma ini bertujuan untuk menentukan  lintasan  terpendek  berdasarkan bobot  terkecil  dari  satu  titik  ke  titik  lainnya. Algoritma Dijkstra melakukan kalkulasi terhadap semua  kemungkinan  bobot  terkecil  dari  setiap titik.  Dengan  kata  lain  algoritma  ini  menghitung lintasan  berdasarkan  jarak  terpendek  yang ditempuh ditiap-tiap kota.
Rumusan  masalah  dari  latar  belakang tersebut yaitu penentuan rute terpendek wilayah Pisangan dengan STMIK Nusamandir Tangerangi, menerapkan Algoritma Dijkstra untuk melakukan kalkulasi  terhadap  semua  kemungkinan  bobot terkecil  dari  setiap  titik.  Sedangkan  batasan masalah dalam penelitian ini adalah 1) Algoritma Dijkstra yang digunakan dibatasi pada permasalahan  shortest  path  saja,  dengan  input graph  yang  terdiri  dari  jumlah  titik,  nama  dan koordinat  titik;  2)  bobot  antara  titik  yang ditentukan  hanyalah  bobot  jarak.  Sehingga  jalur terpendek  berdasarkan  jarak  terpendek  antar titik; 3) dalam Algoritma Dijkstra ini tidak dibahas waktu  dan  kecepatan  transportasi  dari  tempat asal ke tempat tujuan; dan 4) data yang digunakan berasal  dari  informasi  yang  merujuk  ke  kondisi sebenarnya.
Manfaat  Algoritma  Dijkstra  untuk mencari  lintasan  terdekat  (Triansyah,  2014), maka  dapat  membantu  para  pengguna  untuk mengetahui jalur terdekat tanpa harus membuang-buang  waktu.  Sedangkan  tujuan  dari penelitian  ini  antara  lain:  1)  memberikan  solusi
dalam pemilihan lintasan terpendek pada wilayah Pisagan  –  STMIK  Nusamandiri  Tangerang;  2) mempercepat  dalam  mencari  solusi  lintasan terpendek  antara  wilayah  Pisangan  –  STMIK Nusamandiri Tangerang; dan 3) memperoleh hasil yang  akurat  dan  tepat  sesuai  dengan  keadaan  di lapangan.

## BAHAN DAN METODE
Algoritma  Dijkstra  diterapkan  untuk mencari lintasan terpendek pada graf berarah dan graf  tak  berarah.  Algoritma  Dijkstra  mencari lintasan  terpendek  dalam  sejumlah  langkah. Algoritma  ini  menggunakan  prinsip  greedy. Prinsip  greedy  pada  ALgoritma  Dijkstra menyatakan  bahwa  pada  setiap  langkah  kita memilih  sisi  yang  berbobot  minimum  dan memasukannya dalam himpunan solusi (Andayani & Perwitasari, 2014).
Contoh  penerapan  Algoritma  Dijkstra adalah  lintasan  terpendek  yang  menghubungkan antara dua kota berlainan tertentu (Single-source Single-destination  Shortest  Path  Problem).  Cara kerja Algoritma Dijkstra memakai strategi greedy. Setiap  langkah  dipilih  sisi  dengan  bobot  terkecil yang  menghubungkan  sebuah  simpul  lain  yang belum terpilih. Algoritma Dijkstra membutuhkan parameter  tempat  asal  dan  tempat  tujuan.  Hasil akhir  dari  algoritma  ini  adalah  jarak  terpendek dari tempat asal ke tempat tujuan beserta rutenya (Andayani & Perwitasari, 2014)..
Simpul pada graf dapat dinomor dengan huruf a, b, c, … dst, dengan bilangan asli 1, 2, 3, … dst  atau  gabungan  keduanya.  Sisi  yang menghubungkan  simpul  u  dengan  v  dinyatakan dengan  lambing  e1,  e2,  ..  en,  e  adalah  sisi  yang menghubungkan simpul u dengan simpul v makan e  dapat  ditulis  sebagai  e=(u,v).  secara  geometri graf  digambarkan  sebagai  sekumpulan  noktah (simpul)  didalam  bidang  dwimatra  yang dihubungkan  dengan  sekumpulan  garis  (sisi) (Fitria & Triansyah,2011).
Klasifikasi  pada  graf  cukup  luas bergantung  pada  faktor  yang  membedakannya. Berdasarkan  orientasi  arah  pada  sisinya,  maka secara  umum  graf  dibedakan  atas  dua  jenis sebagai berikut (Fauzi, 2011):
1. Graf tidak berarah undirected graph)
Graf  yang  sisinya  tidak  memiliki  orientasi arah  disebut  graf  tidak  berarah.  Pada  graf tidak  berarah  urutan  pasangan  simpul  yang dihubungkan oleh sisi tidak diperhatikan.
2. Graf berarah (directed graph) Graf  yang  setiap  sisinya  diberikan  orientasi arah disebut graf berarah. Pada graf berarah (u,v) dan (v,u) menyatakan dua buah sisi yang berbeda.
Persoalan  mencari  lintasan  terpendek didalam  graf  merupakan  salah  satu  persoalan optimasi.  Graf  yang  digunakan  dalam  pencarian lintasan  terpendek  adalah  graf  berbobot (weighted  graph),yaitu  graf  yang  setiap menyatakan  jarak  antar  kota,  waktu  pengiriman pesan,  ongkos  pembangunan  dan  sebagainya. Asumsi    yang  digunakan  adalah  semua  bobot bernilai  positif.  Kata  terpendek  berbeda-beda maknanya  bergantung  pada  tipikal  persoalan yang akan diselesaikan. Secara umum, terpendek berarti  meminimisasi  bobot  pada  suatu  lintasan dalam  graf.  Algoritma  Dijkstra  merupakan algoritma yang lebih efisien dibanding Algoritma Warshall  meskipun  implementasinya  juga  lebih sukar.  Misalkan  G  adalah  graf  berarah  berlabel dengan  titik-titik  V(G) =  {V1,  V2  …  Vn}  dan  path terpendek  yang  dicari  adalah  dari  V1  ke  Vn. Algoritma  Dijkstra  dimulai  dari  titik  V1  dalam iterasinya, algoritma akan mencari satu titik yang jumlah bobot dari titik 1 terkecil. Titik-titik yang terpilih  dipisahkan  dan  titik-titik  tersebut  tidak diperhatikan lagi dalam iterasi berikutnya.
Dalam  penelitian  ini  pendekatan  yang dilakukan  adalah  melalui  pendekatan  kualitatif. Artinya  data  yang  dikumpulkan  bukan  berupa angka-angka,  melainkan  data  tersebut  berasal dari  naskah  catatan  lapangan,  dokumen  pribadi, catatan,  memo  dan  dokumen  resmi  lainnya. Sehingga  yang  menjadi  tujuan  dari  penelitian kualitatif  ini  adalah  menggambarkan  realita empirik dibalik fenomena secara mendalam, rinci dan  tuntas.  Penggunaan  pendekatan  kualitatif dalam penelitian ini adalah dengan mencocokkan antara realita empirik dengan teori yang berlaku dengan menggunakan metode deskriptif.
Metode  yang  digunakan  untuk  proses pengumpulan data dalam penelitian ini adalah:
1. Metode Pengamatan Langsung (Observation) Dalam  metode  ini  peneliti  melakukan perjalanan  secara  langsung  dari  wilayah Pisangan  ke  Kampus  STMIK  Nusa  Mandiri Tangerang  untuk  mengukur  jarak  melalui tiga rute.
2. Metode Studi Pustaka (Library Research) Pada  tahap  ini  peneliti  mencatat  dan mengutip  pendapat  beberapa  ahli  dan  nara sumber dalam artikel, buku serta surat kabar untuk memperkuat landasan teori.

## HASIL DAN PEMBAHASAN
Penelitian ini menghasilkan suatu program yang  mengimplementasikan  Algoritma  Dijkstra untuk pencarian rute atau jalur terpendek wilayah Pisangan – STMIK Nusa Mandiri Tangerang.
1. Beri  nilai  bobot  (jarak)  untuk  setiap  titik  ke titik  lainnya,  lalu  set  nilai  0  pada  node  awal
dan  nilai  tak  terhingga  terhadap  node  lain (belum terisi).
2. Set  semua  node  “Belum  Terjamah”  dan  set node awal sebagai “Node Keberangkatan”.
3. Dari  node  keberangkatan,  pertimbangkan node  tetangga  yang  belum  terjamah  dan hitung  jaraknya  dari  titik  keberangkatan. Sebagai contoh, jika titik keberangkatan A ke B memiliki bobot jarak 6 dan dari B ke node C berjarak  2,  maka  jarak  ke  C  melewati  B menjadi 6+2=8. Jika  jarak ini lebih kecil dari jarak  sebelumnya  (yang  telah  terekam sebelumnya) hapus  data  lama,  simpan  ulang data jarak dengan jarak yang baru.
4. Saat  kita  selesai  mempertimbangkan  setiap jarak  terhadap  node  tetangga,  tandai  node yang telah terjamah sebagai “Node Terjamah”. Node  terjamah  tidak  akan  pernah  dicek kembali,  jarak  yang  disimpan  adalah  jarak terakhir dan yang paling minimal bobotnya.
5. Set  “Node  Belum  Terjamah”  dengan  jarak terkecil  (dari  node  keberangkatan)  sebagai “Node  Keberangkatan”  selanjutnya  dan lanjutkan dengan kembali ke step 3.
Terdapat  pilihan  rute-rute  yang  dapat  dilalui, diantaranya sebagai berikut:
Sumber : Noviriandini & Safitri (2017) Gambar 1. Rute Pisangan-Kampus STMIK Nusa Mandiri Tangerang
Keterangan: A = Pisangan B = Tanah Merah C = Pondok Jaya D = Sepatan E = Sulang F = Cadas G = Benua H = Bayur I = Pintu Air 10 J = STMIK Nusa Mandiri Tangerang
Dalam hal ini pengguna jalan dapat memilih jalur pertama  yang  diasumsikan  sebagai  jalur
terpendek  untuk  rute  Pisangan  ke  STMIK Nusamandiri Tangerang.
Tabel 1.  Rute 1 Rute 1 Jarak Pisangan 0 km Tanah merah 3,4 km Pondok jaya 1,3 km Sulang 2,9 km Cadas 1,2 km Pintu air 10 6,2 km STMIK Nuri 2,2 km 17,2 km Sumber : Noviriandini & Safitri (2017) Tabel 2.  Rute 2 Rute 2 Jarak Pisangan 0 km Sepatan 5,6 km Sulang 2,7 km Cadas 1,2 km Benua 8,6 km STMIK Nuri 4,9 km 23,0 km Sumber : Noviriandini & Safitri (2017) Tabel 3.  Rute 3 Rute 3 Jarak Pisangan 0 km Bayur 10,5 km Pintu air 10 1,4 km STMIK Nuri 2,2 km 14,1 km
Sumber : Noviriandini & Safitri (2017)
Total  jarak  pada  rute  pertama  adalah  17,2  km, jarak yang paling jauh adalah Cadas menuju Pintu air 10. Total jarak pada rute kedua adalah 23,0 km, jarak  yang  paling  jauh  adalah  Cadas  menuju Benua.  Total  Jarak  pada  rute  ketiga  adalah  14,1 km,  jarak  yang  paling  jauh  adalah  Tanah  merah menuju Bayur.
Perhitungan lintasan terpendek dari simpul awal A ke simpul J
Sumber : Noviriandini & Safitri (2017)
Gambar 2. Langkah Pertama Perhitungan Menggunakan Algoritma Dijkstra Keterangan: Menghitung jarak terpendek dengan
membandingkan  titik  awal  A =  Pisangan  menuju titik B = Tanah Merah, D = Sepatan atau H = Bayur. Dan akhirnya titik yang dituju untuk selanjutnya adalah  titik  B  =  Tanah  Merah  karena  memiliki jarak yang paling kecil.
Sumber : Noviriandini & Safitri (2017) Gambar 3. Langkah Kedua Perhitungan Menggunakan Algoritma Dijkstra
Keterangan: Menghitung jarak selanjutnya dari titik B = Tanah Merah menuju titik C = Pondok Jaya.
Sumber : Noviriandini & Safitri (2017) Gambar 4. Langkah Ketiga Perhitungan
Menggunakan Algoritma Dijkstra
Keterangan: Menghitung  jarak  selanjutnya  dari  titik  C  = Pondok Jaya menuju titik E = Sulang.
Sumber : Noviriandini & Safitri (2017)
Gambar 5. Langkah Keempat Perhitungan
Menggunakan Algoritma Dijkstra
Keterangan: Menghitung jarak selanjutnya dari titik E = Sulang menuju titik F = Cadas
Sumber : Noviriandini & Safitri (2017)
Gambar 6. Langkah Kelima Perhitungan Menggunakan Algoritma Dijkstra Keterangan: Menghitung
jarak terpendek dengan
membandingkan  titik  F  =  Cadas  menuju  titik  I  = Pintu  Air  10  atau  G  =  Benua.  Dan  akhirnya  titik yang dituju untuk selanjutnya adalah titik I = Pintu Air 10 karena memiliki jarak yang paling kecil.
Sumber : Noviriandini & Safitri (2017) Gambar 7. Langkah Terakhir Perhitungan Menggunakan Algoritma Dijkstra
Keterangan: Menghitung jarak terakhir dari titik I = Pintu Air 10  menuju  titik  terakhir  yaitu  titik  J  =  STMIK Nusamandiri Tangerang
Jalan  atau  jalur  yang  dilewati  untuk  perjalanan Pisangan – STMIK Nusa Mandiri Tangerang.
0 1 2 3 4 5 6 7 8 9 A B C D E F G H I J Jarak terpendek A-H-I-J Jadi rute terpendek dari Pisangan ke STMIK Nusa
Mandiri  Tangerang  adalah  14,1  km  melalui Pisangan,  Bayur,  Pintu  Air  10  dan  berakhir  di STMIK Nusa Mandiri Tangerang.

## KESIMPULAN
Berdasarkan  dari  pembahasan  diatas maka  dapat  disimpulkan  bahwa  untuk  mencari jalur  terpendek  antara  wilayah  Pisangan  dengan STMIK Nusa Mandiri Tangerang sudah ditemukan rutenya, yaitu rute pertama dengan jarak tempuh 12,2  km.  Namun  hasil  ini  tidak  menjamin pengguna  jalan  cepat  sampai  ke  tempat  tujuan melainkan  peluangnya  lebih  besar.  Maka diharapkan  pengguna  jalan  dapat  dengan  bijak memilih  jalur  atau  rute  yang  ditempuh  untuk mencapai tempat tujuan yang diinginkan.

## REFERENSI
Fauzi,  Imron.  2011.  Penggunaan  Algoritma Dijkstra  dalam  Pencarian  Rute  Tercepat dan  Rute  Terpendek  (Studi  Kasus  Pada Jalan  Raya  Antara  Wilayah  Blok  M  dan Kota).
Fitria,  dan  Apri  Triansyah.  2011.  Implementasi Algoritma Dijkstra Dalam Aplikasi Untuk Menentukan  Lintasan  Terpendek  Jalan Darat  Antar  Kota  Di  Sumatera  Bagian Selatan.  Konfrensi  Nasional  Teknologi
Informasi dan Aplikasinya.
Noviriandini,  A.  &  Safitri,  M.,  (2017).  Laporan Penelitian  Mandiri.  Jakarta:  STMIK  Nusa Mandiri Jakarta
Sanjaya,  A.,  Sulandari,  E.,  &  Basalim,  S.  (2016). Perencanaan Traffic Light Pada Simpang Jl. Purnama–Jl. M. Sohor-Jl. Letjen Sutoyo Kota Pontianak. Jurnal Mahasiswa Teknik
Sipil Universitas Tanjungpura, 3(3).
Triansyah,  A.  (2014).  Implementasi  Algoritma
Dijkstra Dalam Aplikasi Untuk Menentukan  Lintasan  Terpendek  Jalan Darat  Antar  Kota  Di  Sumatera  Bagian Selatan. Jurnal Sistem Informasi, 5(2).
Utama, V. Y., Kuntjara, A. P., & Sutanto, R. P. (2016). Perancangan  Board  Game  tentang Manajemen Waktu dalam Berlalu Lintas. Jurnal DKV Adiwarna, 1(8), 9.
Warta  Kota.  22  September  2017.  Wali  Kota Tangerang Pantau Titik Kemacetan dan Langsung Tegur Pengendara.
Wibowo, A. G., & Wicaksono, A. P. (2012). Rancang Bangun Aplikasi untuk Menentukan Jalur Terpendek  Rumah  Sakit  di  Purbalingga dengan Metode Algoritma Dijkstra. JUITA (Jurnal Informatika), 2(1).