Implementasi Algoritma Dijkstra Untuk Menentukan Jalur Terpendek Rumah Sakit Di Kota Palembang Rendio Halda1, Ahmad Yani Ranius, S.kom., M.m2, Hadi Syaputra, M.Kom3 Mahasiswa Universitas Bina Darma1,Dosen Universitas Bina Darma23 Universitas Bina Darma, jln Ahmad Yani no 3 Plaju Palembang Email:
[email protected],
[email protected] [email protected]
Abstract : Smartphones Technologies is currently growing very helpful daily activities. The daily activities we often face is to find a location that we do not know. In this study, it will develop an application on smartphones to implement Dijkstra's algorithm into flatporm based operating system Android. This algorithm is chosen because it can determine the shortest path from the graph. This application is expected to allow users of smartphones to locate the nearest hospital in the city of Palembang. Keywords: Dijkstra's algorithm , search the shortest path , Hospitals Abstrak : Teknologi Smartphones yang saat ini sedang berkembang sangat membantu kegiatan sehari-hari. Kegiatan sehari-hari yang sering kita hadapi adalah mencari lokasi yang kita tidak tahu. Pada penelitian ini, akan dikembangkan sebuah aplikasi pada smartphones dengan mengimplementasikan algoritma Dijkstra ke dalam sistem operasi berbasis flatporm Android. Algoritma ini dipilih karena dapat menentukan jalur terpendek dari graph. Aplikasi ini diharapkan dapat memudahkan pengguna smartphones dalam mencari lokasi terdekat Rumah Sakit di Kota Palembang. Kata Kunci : Algoritma Dijkstra, Pencarian jalur terpendek, Rumah sakit
1.
Untuk
PENDAHULUAN Kemajuan
teknologi
orang-orang
yang
sedang
informasi
berkunjung di Palembang dan tidak terlalu
sekarang yang semakin luas dan sangat
mengenal kota Palembang, biasanya akan
berkembang pesat, sehingga dapat membantu
mengalami kesulitan untuk mencari Rumah
masyarakat
untuk
Sakit terdekat. Informasi pelayanan kesehatan
kemudahan
yang
menikmati
oleh
memang sangat berguna bagi masyarakat.
teknologi tersebut. Salah satu aspek teknologi
Informasi ini diharapkan juga berguna jika
yang saat ini sedang berkembang pesat adalah
dalam
teknologi mobile pada perangkat telpon pintar
kecelakaan dalam bekerja, kecelakaan lalu
(smartphone). Teknologi smartphone yang
lintas bagi pengendara kendaraan dan lain-
sedang menjadi incaran masyarakat saat ini
lain.
adalah
sistem
dihasilkan
darurat
seperti
adanya
Berdasarkan beberapa masalah diatas,
akademisi
maka untuk membantu masyarakat dalam
mengembangkan aplikasi berbasis android,
menemukan lokasi Rumah Sakit terdekat di
sehingga dinilai dapat memberikan banyak
wilayah
Kota
manfaat bagi penggunanya.
aplikasi
pencarian
Banyak
operasi
keadaan
berbasis
Android.
adanya
telah
bermacam
kalangan
Palembang, lokasi
dibangunlah Rumah
Sakit
terdekat berbasis mobile platform Android. 1
Android
menjadi
pertimbangan
dalam
1. Mengumpulkan data data Rumah Sakit
mengembangkan aplikasi ini karena perangkat
2. Menganalisis
ini sudah banyak diminati dan digunakan oleh
digunakan
masyarakat. Aplikasi ini akan memberikan
terpendek pada Rumah Sakit
informasi tentang jarak terdekat Rumah Sakit
metode dalam
3. Melakukan
lunak menggunakan
Rumah Sakit tersebut.
Unified Process (RUP).
disebut juga shortest path problem
adalah
salah satu permasalahan yang menarik untuk dianalisa. Shortest path problem adalah sebuah
metode
yang digunakan dalam pencarian jalur terdekat Rumah Sakit 5. Melakukan eksperimen perangkat lunak
perangkat lunak.
yang harus dilalui untuk memperoleh jarak
perangkat
4. Mengimplementasikan metode
titik atau simpul dengan menggunakan bobot
digunakan untuk memberitahukan jalan-jalan
jalur
Rational
dengan
jalur terpendek bisa untuk berbagai hal. Dapat
pencarian
metode
permasalahan dalam mencari jalan diantara 2
yang minimal. Aplikasi dari hasil pencarian
akan
pengembangan
beserta, lokasi, dan alamat yang tersedia di
Pencarian jalur terpendek atau yang
yang
berbagai
6. Melakukan
analisis
masukan
dan
terhadap
pembahasan
terhadap hasil pengujian perangkat lunak 7. Menarik kesimpulan dan membuat laporan penelitian.
terpendek atau bisa saja untuk menyelesaikan
2.2 Metodologi Pengembangan Perangkat
permasalahan yang dapat digambarkan dengan
Lunak
sebuah graf,
dalam permasalah robotic,
Metodologi yang diterapkan dalam
transportasi, dan lain-lain (Setiawan, 2011).
pengembangan perangkat lunak ini adalah
Pencarian lokasi Rumah Sakit terdekat dipilih
Rational
menggunakan
karena
merupakan model pengembangan perangkat
jalur
lunak berorientasi objek dan bersifat iterative
terpendek dari graph berbobot yang bobotnya
incremental.Tahapan yang dilakukan dalam
bernilai lebih besar dari nol (positif), dari titik
penelitian ini adalah sebagai berikut:
awal ke semua titik yang
a.) Fase Insepsi
Algoritma
ini
algoritma
Dijkstra
dapat
menentukan
dikehendaki,
Unified
Process
(RUP)
yang
sehingga nantinya dapat ditemukan jalur terpendek dari titik awal dan titik tujuan yang
dilakukan adalah menganalisa kebutuhan dan
diinputkan.
2.
METODE PENELITIAN
2.1
Metode Penelitian
ruang lingkup aplikasi hangul menggunakan metode graph matching.
Tahap-tahapan yang dilakukan dalam penelitian pencarian jalur terpendek Rumah Sakit
menggunakan
Dijkstra.
Pada fase ini, tahapan yang akan
Metode
Algoritma
b.) Fase Elaborasi Tahapan yang akan dilakukan, yaitu : 1. Melakukan
analisis
perancangan
perangkat lunak menggunakan metode graph matching.
2
dan
2. Mengidentifikasi
arsitektur
perangkat
bernilai lebih besar dari nol ( positif ), dari
lunak berdasarkan use case yang telah
titik awal ke semua titik yang dikehendaki,
dimodelkan pada tahapan insepsi.
sehingga nantinya dapat ditemukan jalur
3. Menggambarkan model kelas analisis, diagram kelas, diagram sekuen,
dan
terpendek dari titik awal dan titik tujuan yang diinputkan. Untuk mempermudah penggunaan
diagram aktivitas dari perangkat lunak
sistem
ini,
maka
pengguna
hanya
menggunakan metode graph matching.
menginputkan tentang informasi titik awal, dan titik tujuan.
c.) Fase Konstruksi Tahapan yang akan dilakukan, yaitu
3.1.1 Analisis Android
1. Memastikan kelengkapan dan kesesuaian
Beberapa kelas yang akan digunakan
antara diagram use case, model kelas
dalam aplikasi menggunakan kelas bawaan
analisis, diagram kelas, dan diagram
yang sudah tersedia dalam Android SDK.
sekuen.
Selain kelas, digunakan juga beberapa widget
2. Membuat kode program yang sesuai dengan
fungsi-fungsi
yang
telah
digambarkan pada fase sebelumnya.
berdasarkan
hasil
Tahap ini berisi identifikasi berbagai widget dan
3. Melakukan pengujian perangkat lunak dan perbaikan
yang dibutuhkan untuk antarmuka aplikasi.
kelas
yang
akan
Pengembangan
aplikasi
dilakukan
menggunakan Android Studio versi 1.2.1.1 (2015).
d.) Fase Transisi Pada
fase
pengujian
ini
akan
terhadap
dilakukan
perangkat
lunak
dengan metodologi pengujian perangkat
3.1.2 Analisis Algoritma Dijkstra Pada
tugas
akhir
ini
digunakan
lunak yaitu, metode white box testing dan
Dijkstra untuk pencarian rute. Algoritma
black box testing.
Dijkstra adalah salah satu metode untuk memecahkan
3.
adalah bagaimana membuat aplikasi pencarian jalur terpendek berbasis android yang dapat mencari jalur terpendek menuju Rumah Sakit ada
di
menyelesaikan digunakan Algoritma
pencarian
rute
pada sebuah aplikasi pencari rute jalan yang
Masalah utama dari tugas akhir ini
yang
masalah
terpendek. Algoritma ini biasanya diterapkan
HASIL
3.1 Analisis Masalah
kota
pencarian
Algoritma ini
Palembang.
dapat
jalur
Untuk
terpendek
Dijkstra menentukan
karena jalur
terpendek dari graph berbobot yang bobotnya 3
tersebut
digunakan dalam aplikasi.
analisis
pengujian
bawaan
terdekat dari suatu daerah ke daerah lainnya. 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 bobotnya dari titik 1 terkecil. Titik-titik yang terpiih dipisahkan dan titik-
titik tersebut tidak diperhatikan lagi dalam
procedure Dijkstra (input m:matriks, a:simpul
iterasi berikutnya. Misalkan:
awal) ( Mencari lintasan terpendek dari simpul awal a
V (G) = {v1, v2,.., vn} L = Himpunan titik-titik ε V (G) yang sudah terpilih dalam jalurpath terpendek.
ke semua simpul lainnya Masukan : matriks ketetanggaan (m) dari graf berbobot G dan simpul awal a
D(j) = Jumlah bobot path terkecil dari v1 ke vj.
Keluaran : lintasan terpendek dari a ke semua simpul lainnya
w(i,j) = Bobot garis dari titik vi ke vj.
)
w*(1,j) = Jumlah bobot path terkecil dari v1 ke
Deklarasi
vj s1, s2, ..., sn :integer (tabel integer) Secara formal, algoritma Dijkstra untuk
d1, d2, ..., dn :integer (tabel integer)
mencari path/rute terpendek adalah sebagai i, j, k: integer
berikut:
Algoritma L = { }; ( langkah 0 (Inisialisasi:)
V = {v2, v3,..,vn}. Untuk i = 2, ..., n, lakukan D(i) – w(1, i)
for i 1 to n do
Selama v si 0
n ∉ L lakukan: a. Pilih titik vk ∈ V - L dengan D(k) terkecil.
di mai
L = L ∪ {vk}
endfor
b. Untuk setiap vj ∈ V - L lakukan: Jika D(j) > D(k) + W(k,j) maka ganti D(j) dengan D(k) + W(k,j)Untuk setiap vj ∈ V,
(langkah 1 :)
w*(1, j) = D(j)
Sa 1 (karena simpul a adalah simpul asal lintasan terpendek, jadi simpul a sudah pasti
Menurut algoritma di atas,
path
terpilih dalam lintasan terpendek )
terpendek dari titik v1 ke vn adalah melalui titik-titik dalam L secara berurutan, dan
Daoo (tidak ada lintasan terpendek dari
jumlah bobot path terkecilnya adalah(n).
simpul a ke a)
Algoritma Dijkstra dinyatakan dalam pseudo-code berikut ini( Rinaldi Munir 2005 , hal. 414):
4
(langkah 2, 3, ..., n-1:) For k 2 to n-1 do
J simpul dengan sj = 0 dan dj minimal 16
Sj 1 {simpul j sudah terpilih ke
35
D
15
9
C
{perbaharui tabel d} For semua simpul I dengan si= 0 do
8
14
12
A
dalam lintasan terpendek}
E
25
B
19
17 22
G 14
F
Gambar 1. Graph berbobot yang menunjukan lokasi dan jarak simpang
If dj+mji
Endif
Hasil Pada Perangkat Lunak
Endfor Endfor )
3.1.2.1 Contoh Perhitungan Rute Terpendek dengan Algoritma Dijkstra Untuk dapat menerapkan algoritma Dijkstra ini dibutuhkan beberapa data yang harus disiapkan, yaitu :
Gambar 2. Tampilan Halaman Rute Awal
1. Beberapa titik/simpul/daerah yang bisa dijangkau secara langsung, dan juga jarak antara
titik-titik
atau
simpul-simpul
tersebut. 2. Titik/simpul/daerah awal. 3. Titik/simpul/daerah tujuan. Sebagai ilustrasi disajikan gambar graph berbobot yang menggambarkan letak dan jarak simpang - simpang A, B, C, D, E, F dan G berikut ini:
5
Plaju Menuju Rumah Sakit Pusri Pada gambar 2. marker yang berwarna hijau
adalah
lokasi
asal
dan
lokasi
akhir,sedangkan marker yang berwarna orange adalah node persimpangan jalan.
penulis menggunakan handphone smartphone android pada versi 4.4.4 (KitKat). Metode pengujian yang digunakan oleh penulis adalah Metode Pengujian Black-Box. Metode
ini
berfokus
pada
persyaratan
fungsional perangkat lunak. Dengan demikian, pengujian
balck
box
memungkinkan
perekayasa perangkat lunak mendapatkan serangkaian kondisi input yang sepenuhnya menggunakan semua persyaratan fungsional untuk suatu program.
Gambar 3.Keterangan jarak antar node Pada gambar 3. merupakan tampilan pada perangkat lunak yang menampilan jarak
Adapun faktor-faktor pengujian blackbox adalah :
antar node(persimpangan).
1. File integrity Menekankan
pada
data
yang
dimasukkan melalui aplikasi akan tidak bisa
diubah.
Prosedur
yang
akan
memastikan bahwa file yang digunakan benar dan data dalam file tersebut akan disimpan sekuensial dan benar. 2. Service levels Menekankan Gambar 4. Hasil Pencarian rute
bahwa
hasil
yang
diinginkan di dapat dalam waktu yang
Pada gambar 4. direction yang berwarna
di inginkan oleh user. Untuk mencapai
biru merupakan hasil rute yang dihasilkan
keinginan tersebut, harus dilakukan
dalam
penyesuaian
pengujian
pada
perangkat
lunak
smartphone android. 3.3 Untuk
antara
keinginan
user
dengan sumber daya yang ada.
Pembahasan menguji
coba
serta
3. Ease of use
menjalankan
perangkat lunak pencarian rute terpendek
Menekankan perluasan usaha yang diminta
pemetaan rumah sakit dengan perhitungan
untuk
algoritma
menyiapakan
6
Dijkstra
berbasis
android
ini,
belajar,
mengoprasikan inputan,
dan dan
menginterpretasikan output dari sistem. Faktor
5. Aplikasi penentuan jarak terdekat Rumah
ini tersangkut dengan usability sistem terhadap
Sakit kota Palembang diimplementasikan
interaksi antara manusia dan sistem.
sebagai
aplikasi
menggunakan 4. Authorization Menjamin
data
android
Java
dengan
sebagai
bahasa
pemrogramannya serta aplikasi database diproses
sesuai
SQLite
dengan
sistem
ini
diharapkan
dapat
Authorization
membantu pengguna dalam menentukan
menyangkut proses transaksi secara umum dan
jalur terpendek Rumah Sakit di kota
khusus. Fokus Pengujian Black box testing
Palembang.
ketentuan
manajemen.
yaitu sebagai berikut :
5.
DAFTAR RUJUKAN
a) Menguji fungsi-fungsi khusus dari aplikasi. Lee. (2011). “Pemograman Aplikasi Mobile b) Test input dan output untuk fungsi yang ada
Smartphone dan Tablet PC
tanpa memperhatikan prosesnya.
Android. Informatika:Bandung”.
Berbasis
Beberapa jenis kesalahan yang dapat di Sapta Antoni. (2010). “Android Database
identifikasi :
Processing 1) Fungsi tidak benar atau hilang,
Menggunakan
Sqlite
Untuk
Rancang Bangun Aplikasi Translator Pada Platform Android”.
2) Kesalahan antar muka, 3) Kesalahan pada struktur data (pengaksesan
Supardi.
basis data),
(2014).
Pemrogram
Aplikasi
Android. Yogyakarta:MediaKom 4) Kesalahan inisialisasi dan akhir program. Kadir.
(2013).
Pemrograman
Java.
Yogyakarta:Andi
4. KESIMPULAN Setelah melalui beberapa proses dalam perancangan dan iplementasi sistem penentuan jarak
terpendek
Dijkstra
maka
menggunakan dapat
algoritma
diambil
beberapa
kesimpulan sebagai berikut : 1. Telah dapat dibuat suatu sistem yang dapat membantu menemukan jarak terdekat menggunakan algoritma Dijkstra. 7
A.S Rosa, Salahuddin M. (2011). “Modul Pembelajaran Rekayasa Perangkat Lunak (Terstruktur dan Berorientasi Objek”. Modula : Bandung. Binanto, Iwan. (2010). Multimedia Digital Dasar Teori. Andi : Yogyakarta.
Nazruddin Safaat H. 2014.
Wirasandy. (2011). “Penyedia Layanan
Pemograman
Aplikasi Mobile Smartphone dan
Pemetaan dan Kartografi Berbasis Web”.
Tablet
PC
Berbasis
Android.
Informatika:Bandung. Azwar. (1996). American Hospital Assication
Stevanie
Joey.
(2012).
“Aplikasi
Laboratorium Kimia Virtual Viclab Sofyan Arifianto. (2010). “ Sistem Aplikasi
Untuk Pelajar SMA Berbasis Android Menggunakan Ligbidx”.
Penerapan Rute Terpendek Pada Jaringan Multi Moda Transportasi Umum Menggunakan Algoritma Dijkstra “ http://jurnal/Sistem%20Aplikasi%20P enentuan%20Rute%20Terpendek
20Pad
a%20Jaringan%20Multimoda%20Tra nsportasi%20Umum.pdf Rosa As dan M Shalahudin. (2013). “Rekayasa Perangkat Lunak Terstruktur dan Berorientasi Objek”. Informatika, Bandung.
Setiawan, W. (2010). “Pembahasan Pencarian Lintasan Terpendek Menggunakan Algoritma Dijkstra dan A*” .
Irwan Iftadi, Wakhid Ahmad Jauhari, dan Beny Nugroho. (2011) “ Perancangan Peta Evakuasi Menggunakan Algoritma FloydWarshall Untuk Penentuan
Lintasan
Terpendek “. Finsa Ferdifiansyah. (2012). ” Perbandingan Algoritma Dijkstra Dan Algoritma
Ant
Colony Dalam Penentuan Jalur Terpendek”.
8
Tri Listyorini, (2013). “Perancangan Mobile Learning Mata Kuliah Sistem Operasi Berbasis Android”.
