## Implementasi Algorithma Dijkstra Dalam Pencarian Rute Terpendek Fasilitas Kesehatan Tingkat I (Studi Kasus BPJS Kesehatan Kota Bengkulu)
Ardi Wijaya 1 , Edo Kurniawan 2
Program Studi Teknik Informatika Fakultas Teknik Universitas Muhammadiyah Bengkulu Jln.Bali (Telp. (0736) 22027, 22765 Fax.
(0736) 26161; e-mail: penulis1@institusi.ac.id) 1 ardiwijaya@umb.ac.id, 2 Edo_kurniawan@gmail.com
Abstract —Faskes or in English is Health facilities are the first- level health facilities and become the first place for society to get treatments  or  medicines. If this first Health Facilities  are not able viewed in the context of human resources or medical equipment,  the  patients  will  be  recommended  to  send  to  a further health facility. According to Munir (2010: 4), that the Djikstra  algorithm  is  named  based  on  the  inventor's  name namely  Djikstra  Edsger.  The  Djikstra  algorithm  applied  the greedy principle, where in every step was selected a side with a minimum weight that connected to a  chosen  node to  another node that has not been selected yet. Web application afford to assign  the  shortest  route  until  it  can  facilitate  users  in searching  for  health  facilities  at  the  close-in  distance.  This application employed Google Maps to display health facilities location  data,  routes  to  destinations,  and  others.  This application hopefully performs frequent data update so as this application can follow GIS technology development.
Keywords: Health facilities, Djikstra, Website, Maps
Intisari —Faskes  adalah  singkatan  dari  fasilitas  kesehatan, sedangkan  1  adalah  tingkat  pertama,  jadi  faskes  1  artinya fasilitas  kesehatan  tingkat  pertama  dan  menjadi  tempat pertama  yang  harus  didatangi  peserta  jika  ingin  berobat, apabila  Faskes  1  tidak  sanggup  baik  dari  segi  sumber  daya manusia maupun peralatan medis maka peserta akan dirujuk ke faskes lanjutan. Algoritma Djikstra dinamai sesuai dengan nama  penemunya  yaitu Edsger  Djikstra .  Algoritma Djikstra menggunakan  prinsip greedy, dimana  pada  setiap  langkah dipilih  sisi  dengan  bobot  minimum  yang  menghubungkan sebuah  simpul  yang  sudah  terpilih  dengan  simpul  lain  yang belum terpilih [1]. Aplikasi Web yang dapat menentukan rute terpendek  sehingga  dapat  memudahkan  pengguna  dalam melakukan  pencarian  fasilitas  kesehatan  dengan  jarak terdekat.  Aplikasi  ini  menggunakan  Google  Maps  untuk menampilkan  data  lokasi  fasilitas    kesehatan,  menampilkan rute ke tujuan, dan lainnya. Untuk menggunakan Google Maps pada  aplikasi  ini.  Diharapkan  aplikasi  ini  selalu  melakukan update data  sehingga  aplikasi  ini  mengikuti  perkembangan teknologi GIS Kata Kunci : Faskes, Djikstra, Website, Maps

## I. PENDAHULUAN
Dengan perkembangan teknologi informasi, peta tidak berupa  lagi  lembaran  ataupun  buku.  Saat  ini  terdapat layanan  peta  secara  digital  yang  sudah  ditanamkan  pada perangkat  bergerak.  Kelebihan  dari  peta  ini  adalah memudahkan  pengguna  dalam  mencari  lokasi  suatu
tempat.  Algoritma Djikstra dinamai  sesuai  dengan  nama penemunya  yaitu Edsger  Djikstra .  Algoritma Djikstra menggunakan prinsip greedy, dimana pada setiap langkah dipilih sisi dengan bobot minimum yang menghubungkan sebuah simpul yang sudah terpilih dengan simpul lain yang belum terpilih [1].
Faskes  adalah  singkatan  dari  fasilitas  kesehatan, sedangkan 1 adalah tingkat pertama, jadi faskes 1 artinya fasilitas  kesehatan  tingkat  pertama  dan  menjadi  tempat pertama yang harus didatangi peserta jika ingin berobat, apabila  Faskes  1  tidak  sanggup  baik  dari  segi    sumber daya manusia maupun peralatan medis maka peserta akan dirujuk ke faskes lanjutan.
Setiap  orang  dalam  melakukan  perjalanan  pasti memilih  rute  terpendek  untuk  mencapai  tujuannya, karena  dapat  menghemat  waktu  dan  tenaga,  dalam aplikasi  yang  dibangun  tersebut  nantinya  akan ditanamkan  algoritma  yang  berfungsi  sebagai  pencari rute  terpendek  lokasi  fasilitas  kesehatan  tingkat  1,  dan algoritma  yang  digunakan  adalah  algoritma Djikstra , algoritma  ini  akan  membandingkan  bobot  terkecil  dari node awal sampai ke node tujuan untuk menemukan jalur paling efisien.
Penerapan  algoritma Djikstra merupakan  salah  satu langkah  atau  cara  untuk  membantu  dalam  menentukan pencarian rute manakah yang terdekat dengan lingkungan tempat  tinggal  calon  anggota  BPJS  kesehatan,  untuk mempermudah menentukan Fasilitas Kesehatan Tingkat 1 (satu).
Untuk mengatasi
permasalahan ini maka  diperlukan  suatu  aplikasi Web yang  dapat menentukan rute terpendek sehingga dapat memudahkan
pengguna dalam melakukan pencarian fasilitas kesehatan dengan jarak terdekat.

## II. T INJAUAN P USTAKA
Sistem  pengolahan  data  berkembang  sangat  cepat seiring  dengan  pesatnya  perkembangan  teknologi komputer. Salah satu sistem pengolahan data yang sangat popular di beberapa negara maju, khususnya dalam bidang survei  dan  pemetaan  adalah  Sistem  Informasi  Geografis (SIG) [2].
A. Sistem Informasi Geografis
Pada  dasarnya,  istilah  Sistem  Informasi  Geografis (SIG)  merupakan  gabungan  dari  tiga  unsur  pokok  yaitu sistem, informasi dan geografis. Dengan melihat unsur- unsur tersebut,  maka  jelas  SIG  merupakan  salah  satu  sistem informasi  yang  menekankan  pada  unsur  “informasi geografis”. SIG terdiri dari data spasial dan aspasial [3].
B. Peta
Peta merupakan penyajian grafis dari permukaan bumi dalam  skala  tertentu  dan  digambarkan  pada  bidang  datar melalui sistem proyeksi peta denganmenggunakan simbol- simbol  tertentu  sebagai  perwakilan  dari  objek-  objek spasial  di  permukaan  bumi.  Peta  mengandung  arti komunikasi, artinya peta merupakan suatu alat penyampaian  sinyal  atau  saluran  informasi  antara  si pengirim  pesan  (pembuat  peta)  dan  si  penerima  pesan (pemakai peta) [4].
Agar  komunikasi  tersebut  berjalan  lancar  maka  sebuah peta harus memiliki syarat-syarat sebagai berikut:
1. Peta  tidak  boleh  membingungkan,  dalam  hal  ini  peta perlu dilengkapi ketarangan/legenda, skala, judul peta, bagian dunia mana.
2. Peta harus dapat dimengerti atau ditangkap maknanya oleh  sipemakai  peta  supaya  mudah  dimengerti  atau ditangkap  maknanya, dan  yang perlu digunakan ialah tata  warna,  symbol,  dan  system  proyeksi  dan  system kordinat.
3. Pada  harus  memberikan  gambaran  yang  sebenarnya tingkat ketelitian harus disesuaikan dengan tujuan dan jenis  peta,  serta  kesanggupan  skala  peta  itu  dalam menyatakan ketelitian.
C. Basis Data
Basis data merupakan kumpulan dari data yang saling berhubungan  satu  dengan  yang  lainnya,  tersimpan diperangkat  keras  komputer  dan  digunakan  perangkat lunak  untuk  memanipulasinya.  Penerapan  basis  data (database)  dalam  sistem  informasi  disebut  juga  dengan database system [5].
D. Pencarian Rute Terpendek
Lintasan  terpendek  adalah  jarak  yang  ditempuh  dari suatu  titik  ke  titik  yang  lain  dengan  jarak  tempuh  yang paling pendek. Untuk mencari lintasan terpendek dalam suatu graph, berarti  membicarakan  masalah  optimasi. Graph yang digunakan dalam mencari lintsan terpendek, menggunakan graph berbobot.  Bobot  pada graph bisa berupa  jarak,  waktu,  biaya  dan  sebagainya.  Biasanya, bobot  yang  ada  pada graph berupa  nilai  positif.  Tetapi tidak  menutup  kemungkinan  terdapat  nilai  yang  negatif [6].  Ada  beberapa  istilah  yang  berhubungan  dengan graph , antara lain:
1. Vertex
Vertex  adalah  himpunan  node/titik  pada  sebuah
graf
2. Edge
Edge adalah himpunan garis yang menghubungkan tiap node/vertex
3. Graf  berarah  dan  tidak  berbobot:  tiap  busur mempunyai anak panah yang tidak berbobot.
Graf tidak berarah dan tidak berbobot: tiap busur tidak mempunyai anak panah dan tidak berbobot
Gambar 1. . Contoh Pencarian Rute Terpendek

## III. M ETODOLOGI PENELITIAN
Metodologi  pengembangan  sistem  menggunakan pendekatan  Rapid  Application  Development  (RAD)
yang  menekankan  pada  siklus  pembangunan  pendek, singkat,  dan  cepat  [7].  Waktu  yang  singkat  adalah batasan  yang  penting  untuk  model  ini.  RAD menggunakan metode iteratif (berulang) dalam mengembangkan  sistem dimana  working  model (model bekerja)  sistem  dikonstruksikan  di  awal  tahap pengembangan  dengan  tujuan  menetapkan  kebutuhan (requirement) user dan selanjutnya disingkirkan.Berikut ini  adalah  gambaran  kerangka  pemikiran  dari Rapid Aplication  Development (RAD),  dapat  dilihat  pada Gambar 1.

## Gambar 1. Kerangka Kerja RAD
A. Analysis And Quick Design
1. Tahapan Pengumpulan data
a) Observasi Dalam  hal  ini  observasi  dilakukan  secara formal maupun informal untuk mengamati secara  kualitatif  berbagai  kegiatan  yang terjadi. Dalam penelitian ini perlu dilakukan  observasi  untuk  memperoleh informasi    yang  lebih  spesifik  tentang alamat  fasilitas  kesehatan  tingkat  I  pada BPJS Provinsi Bengkulu dan pengambilan data  koordinat  lokasi  fasilitas  kesehatan tingkat  I  menggunakan software pada
playstore yaitu latitude longitude location .
b) Wawancara
Wawancara dilakukan  kepada pihak BPJS
Provinsi Bengkulu sebagai pusat data.
c) Studi Pustaka
Studi  Pustaka  yaitu  pengumpulan  data  yang besumber  dari  arsip/dokumen  yang  terdapat pada  BPJS  Provinsi  Bengkulu,  selain  itu  juga menggunakan  data  yang  bersumber  dari  buku kepustakaan, hasil penelitian dan arsip/dokumen  yang  berhubungan  dengan
penelitian ini.
2. Penjelasan Hardware dan Software
Sistem ini akan dibangun berbasis web sehingga penjelasan  hardware  dan  software  dirasa  cukup penting demi kelancaran dalam proses membangun  sistem  ini.  Adapun  spefikasi hardware  yang  diperlukan  dalam  membangun sistem  ini  adalah  minimal  laptob  atau  Personal Komputer  dengan  kemampuan  processor  intel core  i3  ditunjang  dengan  RAM  minimal  2GB serta media penyimpanan HDD 500GB. Adapun Software  yang  digunakan  dalam  membangun sistem  ini  adalah,  1.  Sistem  Operasi  berupa Windows  7,
2. Aplikasi berupa Dreamweaver dan XAMPP.
B. Prototype Cycles
1. Rancangan File
Digram koteks pada gambar 3.2 di bawah ini  menggambarkan  tentang  proses  kerja sistem  ini  secara  umum.  Admin  dapat melakukan input data  wilayah, input data faskes,  data  peserta  dan  data  admin  pada sistem  informasi  geografis,  Sedangkan peserta  dapat  menerima  informasi  peta lokasi faskes terdekat.
Gambar 2. Diagram Konteks
Gambar 3. Diagram Alir Data Level
2. Rancangan Interface
a. Rancangan Menu Awal
Menu  Awal  ini  adalah  menu  utama  yang akan  kita  jumpai  ketika  pertama  kali menggunak sistem ini.
Gambar 4. Form Rancangan Menu Awal
b. Rancangan  Peta  Fasilitas  Kesehatan  Pada rancangan  fasilitas  kesehatan
merupakan tampilan peta    fasilitas kesehatan  dan  akan  ditampilkan  pada  peta maps.
Gambar 5. Form Peta Fasilitas Kesehatan
Gambar.6.  Form  Rancangan  Jalur Terpendek
Setelah proses tahapan dari rancangan file dan rancangan interface selesai, maka tahapan yang akan selanjutnya  dilakukan  adalah  tahapan  program. Tahapan ini merupakan proses pengkodean rancangan kedalam sistem yang akan dibangun.
C. Testing
Setelah  tahapan  pengkodingan  sistem  selesai dilakukan, maka tahapan selanjutnya adalah menguji sistem  ini  dengan  mengaplikasikannya  langsung kepada beberapa pengguna, alat pengukurnya berupa penilaian kuisoner terhadap pengguna yang
menggunakan sistem ini. Jika dirasa nilai dan tingkat kepuasan terhadap sistem ini cukup, maka sistem ini siap untuk di implementasikan.

## D. Implementasi
Setelah semua proses rangkaian ini selesai dilakukan maka  tahapan  selanjutnya  adalah  implementasi sistem.

## IV. HASIL DAN PEMBAHASAN

## A. Hasil
Aplikasi  Pencarian  Rute  Terpendek  Untuk  Menentukan Fasilitas Kesehatan Tingkat 1. Aplikasi ini mempunyai dua jenis  halaman,  yaitu  halaman  utama  yang  bersifat  umum untuk  pengunjung  dan  halaman  admin  yang  digunakan administrator untuk mengelola data. Adapun gambaran awal dari graf faskes tingkat I adalah sebagai berikut :
Gambar 7. Rute 1
Adapun daftar urut graf berdasarkan Jl.S Parman No 18, ke Jl. Jawa No 31 berdasarkan graf adalah sebagai berikut :
1. Menentukan  objek  faskes  dengan  koordinat sebagai berikut: a. PKM
Sukamerindu (- 3.7882791, 102.267327).
2. Menentukan  graf  berdasarkan  koordinat  objek faskes.  Jadi  untuk  menghitung  rute  dari  Jl.S Parman No 18 ke Jl. Jawa No 31 adalah sebagai berikut :
Dalam  penentuan  graf,  setiap  node  memiliki satuan  meter.  Jadi  setiap  node  akan  mencari satuan meter yang terpendek. a. Penentuan Ruas Pertama
Gambar 8. Rute 2
b. Penentuan Ruas Kedua
Gambar 9. Rute 3
c. Penentuan Ruas Ketiga Gambar 10. Rute 4
d. Penetuan Ruas Keempat Gambar 10. Rute 5
e. Penentuan Ruas Kelima Gambar 10. Rute 6
f. Penentuan Ruas Keenam
Gambar 10. Rute 8
Jadi untuk menghitung rute dari Jl.S Parman No 18 ke Jl. Jawa No31 adalah sebagai berikut:
a. Titik Hijau ke titik merah alternatif 1 (jalur merah) = 0.025+0.053+0.090+0.6+0.5+0.7+0.2 =
b. 2.017 Km.
c. Titik  Hijau  ke  titik  merah  alternatif  2  (jalur hijau) = 0.025+0.053+0.090+0.4+0.4+0.1+0.7+0
i. .2= 2.006 Km d. Titik  Hijau  ke  titik  merah  alternatif  3  (jalur biru) = 0.025+0.053+0.090+0.7+0.3+0.7+0.2= i. 2.026 Km
Jadi rute terbaik adalah rute pilihan alternatif yang ke dua (b), yaitu dengan jarak 2,006 Km.

## B. Pengujian Sistem
Pengujian  sistem  dilakukan  setelah  Aplikasi Implementasi Algoritma Dijkstra Dalam Pencarian Rute Terpendek  Untuk  Menentukan  Fasilitas  Kesehatan Tingkat 1 yang dibuat telah selesai. Pengujian Kuisoner yang  dilakukan  bertujuan  menambah  nilai  siklus  hidup pengembangan  perangkat  lunak  karena  memungkinkan pelanggan  sebenarnya  kesempatan  untuk  memberikan masukan  ke  dalam  desain,  fungsi,  dan  kegunaan  dari produk.  Masukan  ini  tidak  hanya  penting  untuk keberhasilan produk tetapi juga investasi ke produk masa depan  ketika  data  yang  dikumpulkan  dikelola  secara efektif.
Table 1 Pengujian Beta
Keterangan :
1. Jumlah Pernyataan :
- Sangat Menarik = 47 Pernyataan
-Menarik = 45 Pernyataan
-Tidak  Menarik  =  8  Pernyataan
Total = 100 pernyataan
2. Jumlah Responden : 20 Responden
Maka  diperoleh  jawaban  sangat  menarik 47  % , menarik 45 %, dan tidak  menarik 8% .  Adapun cara perhitungannya adalah sebagai berikut :
1. Hitung setiap row pernyataan kemudian pernyataan dijumlahkan.
2. Lakukan perhitungan
a. Sangat menarik = 47%
b. Menarik = 45 %
c. Tidak Menarik = 8%
Hasil rincian dari perhitungan di atas dapat dilihat pada gambar 11 di bawah ini:
Gambar 11. Persentase Hasil Pengujian Sistem

## V. PENUTUP

## A. Kesimpulan
Berdasarkan hasil pembahasan dan pengujian  dapat  diambil  kesimpulan  sebagai berikut :
1. Menghasilkan  aplikasi  berbasis web yang  dapat menentukan rute terpendek.
2. Mengimplementasikan  algoritma Djikstra agar  dapat menentukan rute terpendek.
3. Membantu  kantor BPJS kesehatan dengan  mudah dan cepat  dalam  pencarian  fasilitas  kesehatan  tingkat  1 manakah  yang  paling  terdekat  di  lingkungan  tempat tinggal peserta BPJS kesehatan.

## B. Saran
Dari  kesimpulan  diatas,  ada  beberapa  saran  agar dapat  menggunakan  program  aplikasi  ini  dengan maksimal
1. Aplikasi  ini  selalu  melakukan update data  sehingga aplikasi ini mengikuti perkembangan teknologi GIS.
2. Aplikasi  ini  dapat  dikembangkan  pada  kasus  lainnya sehingga dapat menambah wawasan pada pemograman PHP dan MAP
D AFTAR P USTAKA [1] Munir, R., Matematika Diskrit,  4,
413-414, Informatika, Bandung, 2010
[2] KHARISTIANI,  Erna;  ARIBOWO,  Eko.  Sistem Informasi  Geografis  Pemetaan  Potensi  SMA/SMK Berbasis Web  (Studi  Kasus:  Kabupaten  Kebumen). Jurnal Sarjana Teknik Informatika , 2013, 2.1: 41-49.
[3] Prahasta,  Eddy,  2002,  Konsep-Konsep  dasar  Sistem Informasi Geografis, Informatika, Bandung.
[4] Riyanto,  Putra,  P.  E.,  &  Inderlako,  H.  (2009). Pengembangan  Aplikasi  Sistem  Informasi  Geografis Berbasis Desktop dan Web. Yogyakarta: Gava Media.
[5] Jogiyanto, 2005, Pengenalan Komputer,  Andi, Yogyakarta
[6] Yusuf,  M.  S.,  Az-Zahra,  H.  M.,  &  Apriyanti,  D.  H. (2017).  Implementasi  Algoritma  Djikstra  Dalam Menemukan Jarak Terdekat Dari Lokasi Pengguna Ke Tanaman  Yang  Di  Tuju  Berbasis  Android.  Jurnal Pengembangan  Teknologi  Informasi  dan  Ilmu Komputer , 1779-1787.
[7] Pressman,  R.  S.  (2005).  Software  engineering:  a practitioner’s approach. Palgrave Macmillan