1 BAB IV HASIL DAN PEMBAHASAN 4.1 Hasil Penelitian Pengumpulan Data Pada tahap ini penulis mengumpulkan data-data berupa nama dan titik koordinat loka...
4.1.1 Pengumpulan Data Pada tahap ini penulis mengumpulkan data-data berupa nama dan titik koordinat lokasi Apotik, Mall dan Supermarket. Data tentang apotik, mall dan supermarket dapat dilihat pada lampiran. 4.1.2 Identifikasi Data Identifikasi data bertujuan untuk mengetahui variabel yang dibutuhkan dalam pembuatan sistem. Pada tahap ini peneliti melakukan analisa dan seleksi data mengenai perhitungan nilai jarak minimum berdasarkan titik-titik atau lokasilokasi gedung apotik, mall dan supermarket. 4.1.3 Pembuatan Aplikasi a.
Analisis Kebutuhan Sistem Analisis kebutuhan sistem membahas secara garis besar kebutuhan sistem.
Sistem yang dibangun ini melibatkan dua aktor yakni admin dan user. Aktifitas admin meliputi proses login admin, input data lokasi apotik, mall dan supermarket, sedangkan user melakukan proses mengakses informasi lokasi apotik, mall dan supermarket serta mencari rute tercepat yang dapat dilalui dari apotik satu menuju apotik lainnya atau dari mall dan supermarket yang satu ke mall dan supermarket lainnya.
1
b. Desain Sistem 1) Arsitektur Sistem Berikut adalah rancangan arsitektural dari Sistem Informasi Geografis Untuk Menentukan Rute Terpendek Menggunakan Algoritma Dijktra:
Web Server Internet
Komputer User Database
Gambar 4.1 Arsitektur Sistem Aplikasi ini nantinya akan diimplementasikan berbasis web, dimana aplikasi ini membutuhkan koneksi internet untuk menampilkan peta Google Maps dan mengakses database online melalui perantara webserver berupa script PHP.
2
2) Rancangan Proses a) Diagram konteks
ADMIN
- Data admin - Data lokasi SIG MENENTUKAN RUTE TERPENDEK DENGAN MENGGUNAKAN ALGORITMA DIJSKTRA
-
Map tiap-tiap lokasi Data lokasi Jarak dan rute tercepat dari tiap-tiap titik Rute map
USER Lokasi awal dan lokasi tujuan
Gambar 4.2 Diagram Konteks
3
b) DAD Level 0
Admin
Data admin
- Data admin - Data lokasi
Admin
1.0 Input
- Map tiap-tiap lokasi - Data lokasi
Data lokasi
Lokasi
2.0 Sebaran lokasi
Lokasi awal dan lokasi tujuan
User - Jarak dan rute tercepat dari tiap-tiap titik - Rute map
Data Lokasi
3.0 Kalkulasi jarak & pemetaan rute
Data lokasi
Lokasi
Gambar 4.3 DAD Level 0 c) DAD Level 1 Proses 1 (Input)
Data admin
1.1P Input Data Admin
Data admin
Admin
Admin
Data lokasi
1.2P Input Data Lokasi
Data lokasi
Gambar 4.4 DAD Level 1 Proses 1 4
Lokasi
d) DAD Level 1 Proses 3 (Kalkulasi Jarak & Rute)
User
3.1P Kalkulasi Jarak & Rute
Lokasi awal dan lokasi tujuan
Hasil kalkulasi
3.2P Pemetaan Hasil Kalkulasi Jarak & Rute
- Rute map - Jarak dan rute tercepat dari tiap-tiap titik
Gambar 4.5 DAD Level 1 Proses 3
3) Desain Database Sistem Informasi Geografis ini menggunakan database Myqsl yang terdiri dari 2 tabel yakni tabel admin dan tabel lokasi. a. Table admin - Nama Tabel
: admin
- Primary Key
: id
- Foreign Key
:
- Fungsi
: menyimpan data admin
5
Tabel 4.1 Tabel Admin Field
Type Id Int(2) Username Varchar(10) Password Varchar(32)
Null
Key PRI
Default
Extra AUTO_INCREMENT
Default
Extra AUTO_INCREMENT
b. Table Lokasi - Nama Tabel
: lokasi
- Primary Key
: no
- Foreign Key
:
- Fungsi
: menyimpan data lokasi
Table 4.2 Tabel Lokasi Field No Tempat Alamat Lat Lon
Type Int(3) Varchar(50)
Null
Key PRI
Text
Double Double
Neighboard Text Image
Text
Kategori
Varchar(10)
4) Desain Antar Muka (Interface) a. Rancangan Tampilan Halaman Utama Pada tampilan halaman utama terdapat 2 button kategori yaitu apotik serta mall dan supermarket seperti terlihat pada gambar 4.6 berikut:
6
Gistra Gorontalo
Apotik
Mall & Supermarket
SELAMAT DATANG
Apa Itu DIJKSTRA
Cara Menggunakan Gistra Kritik & Saran
Selengkapnya
Selengkapnya
Selengkapnya
Gambar 4.6 Rancangan Tampilan Utama b. Rancangan Halaman Peta Sebaran Lokasi Halaman peta sebaran lokasi menampilkan peta dari tiap-tiap titik lokasi yakni berupa icon–icon dari lokasi fasilitas yang sudah ditetapkan terlebih dahulu, seperti terlihat pada gambar 4.7 berikut:
Gistra Gorontalo Google Map With Dijkstra Map view
Satellite view
Direction
[icon] Nama Lokasi [icon] Nama Lokasi Nama lokasi
[icon] Nama Lokasi [icon] Nama Lokasi [icon] Nama Lokasi [icon] Nama Lokasi
Gambar 4.7 Rancangan Peta Sebaran Lokasi 7
c.
Rancangan Kalkulasi Jarak dan Rute Halaman kalkulasi jarak & rute ini menampilkan total jarak yang ditempuh
dan rute tercepat yang akan dilalui dari lokasi awal sampai ke lokasi tujuan, seperti terlihat pada gambar 4.8 di bawah ini:
Gistra Gorontalo
Lokasi Awal
Mall & Supermarket
Apotik
Kalkulasi
start
Lokasi Tujuan Rute yang dilalui : ………….. ………..... …………… ……………
fisnish
Jarak yang ditempuh : ……….. Show on map
Gambar 4.8 Rancangan Kalkulasi Jarak dan Rute d. Rancangan Login Admin Halaman login admin merupakan halaman untuk admin melakukan login agar dapat masuk ke halaman admin. Halaman login admin ini dapat dilihat pada gambar 4.9 berikut:
Rancangan Halaman Admin Halaman admin ini merupakan halaman untuk admin melakukan
manipulasi data seperti input data lokasi, edit, dan menghapus. Halaman admin ini dapat dilihat pada gambar 4.10 berikut: Database location Apotik
Database Nama tempat
Alamat
Latitude
Longitude Neighbours
Mall & Supermarket
Edit
Hapus
Edit
Hapus
Edit
Hapus
Edit
Hapus
Edit
Hapus
Edit
Hapus
Tambah
Gambar 4.10 Rancangan Halaman Admin
9
f.
Rancangan Halaman Input Halaman input merupakan halaman untuk menginput ataupun menambah
data lokasi apotik atau mall dan supermarket. Halaman input ini dapat dilihat pada gambar 4.11 di bawah ini: Tambah lokasi Gambar
Browse
Nama tempat Alamat Latitude Longitude Neighbours
Submi t
Reset
Gambar 4.11 Rancangan Halaman Input g.
Rancangan Halaman Edit Halaman edit merupakan halaman untuk mengubah data lokasi apotik
ataupun mall dan supermarket. Halaman edit ini dapat dilihat pada gambar 4.12 berikut ini: Edit lokasi Gambar
Browse
Nama tempat Alamat Latitude Longitude Neighbours
Submi t
Reset
Gambar 4.12 Rancangan Halaman Edit 10
4.1.4 Implementasi Implementasi aplikasi penentuan rute tercepat dengan menggunakan algoritma dijsktra diaplikasikan berbasis web. Adapun tampilan dari aplikasi penentuan rute tercepat dengan menggunakan algoritma dijsktra adalah sebagai berikut: 1) Tampilan Halaman Awal Halaman ini merupakan halaman awal ketika user mengkases website ini. Halaman ini terdiri dari 2 menu kategori yaitu Apotik serta Mall dan Supermarket. Halaman awal ini dapat dilihat pada gambar 4.13 berikut ini:
Gambar 4.13 Tampilan Halaman Awal 2) Tampilan Halaman Login Admin Halaman ini berisi form untuk memasukan username dan password dan tombol login. Untuk mengakses halaman admin harus login terlebih dahulu. Halaman login admin dapat dilihat pada gambar 4.14 berikut:
11
Gambar 4.14 Login Admin 3) Tampilan Halaman Admin Halaman ini merupakan halaman admin untuk melakukan manipulasi data. Pada halaman ini terdapat menu kategori apotik serta mall dan supermarket, menu add new record yaitu untuk menginput data apotik ataupun mall dan supermarket, Edit, Delete serta Logout untuk keluar dari halaman admin. Halaman admin dapat dilihat pada gambar 4.15 berikut ini:
Gambar 4.15 Tampilan Halaman Admin
12
4) Tampilan Halaman Input Lokasi Halaman ini merupakan halaman untuk menginput data lokasi apotik atau mall dan supermarket. Halaman input lokasi ini dapat dilihat pada gambar 4.16 di bawah ini:
Gambar 4.16 Halaman Input Lokasi 5) Tampilan Halaman Edit Halaman ini merupakan halaman untuk mengubah data lokasi apotik atau mall dan supermarket. Halaman edit ini dapat dilihat pada gambar 4.17 di bawah ini:
Gambar 4.17 Halaman Edit Data Lokasi 13
6) Tampilan Halaman Hapus Halaman ini merupakan halaman untuk admin menghapus data lokasi. Halaman ini sama dengan halaman awal admin, dimana pada halaman ini admin dapat langsung mengklik icon tempat sampah untuk menghapus data, seperti terlihat pada gambar 4.18 di bawah ini:
Gambar 4.18 Halaman Hapus Data Lokasi 7) Tampilan Halaman Peta Sebaran Lokasi Pada halaman ini ditampilkan peta sebaran titik-titik lokasi apotik ataupun mall dan supermarket. Terdapat 5 command button yaitu Apotik, Mall dan Supermarket, Map View, Satellite View dan Direction. Tombol Apotik berfungsi untuk menampilkan titik-titik apotik, tombol Mall dan Supermarket berfungsi untuk menampilkan titik-titik Mall dan Supermarket, tombol Map View berfungsi untuk menampilkan peta dalam bentuk map, Satellite View berfungsi untuk menampilkan peta dalam bentuk foto satelit dan tombol Direction berfungsi untuk menampilkan form kalkulasi jarak dan rute. Halaman Peta Sebaran lokasi dapat dilihat pada gambar 4.19 berikut ini:
14
Gambar 4.19 Halaman Peta Sebaran Lokasi 8) Tampilan Kalkulasi Jarak dan Rute Ketika user mengklik direction, maka sistem akan berpindah ke halaman selanjutnya yaitu Kalkulasi Jarak dan Rute. Pada halaman ini user akan memilih lokasi awal dan lokasi tujuan. Selanjutnya user akan mengklik button kalkulasi jarak maka sistem akan menampilkan jarak yang akan ditempuh dan rute yang akan dilalui dari lokasi awal menuju ke lokasi tujuan, seperti terlihat pada gambar 4.20 di bawah ini:
Gambar 4.20 Tampilan Kalkulasi Jarak dan Rute 15
Setelah kalkulasi jarak ditampilkan, maka langkah selanjutnya user akan mengklik button Show on Map, dimana pada tahap ini sistem akan menampilkan rute yang akan dilalui dalam bentuk peta, serperti terlihat pada gambar 4.21 di bawah ini:
Gambar 4.21 Tampilan Rute yang akan dilalui 9) Penerapan Algoritma Dijsktra Sistem yang dibangun ini ialah sistem informasi untuk menentukan rute tercepat yang akan dilalui dengan menggunakan algoritma dijsktra. Berikut contoh penerapan algoritma dijsktra dari Q-Mart menuju ke Santika Dept. Store:
16
Q-Mart (5) Amanda Jaya (0) Mega Zanur Mall (4)
Makro Dept. Store (3)
Gorontalo Mall (1)
Virgo (7)
Karsa Utama (2)
Santika Dept. Store (6)
Gambar 4.22 Graf Mall dan Supermarket function dijkstraz(Awal,Akhir) { Awal = parseInt(Awal); Akhir = parseInt(Akhir); JumlahVerteks = jarak.length; var Posisi= new Array(JumlahVerteks); var Kunjungan = new Array(JumlahVerteks); var Sebelum= new Array(JumlahVerteks); var TakTerdefinisi = -1; var i; var Verteks; var Berhenti; var iframe = document.getElementsByTagName('iframe')[1]; var debug1 = document.getElementById('debug').checked; var doc = iframe.contentWindow.document; doc.body.innerHTML = ""; for(i=0; i<JumlahVerteks; i++) { Posisi[i]= NilaiAcuan; Sebelum[i]= TakTerdefinisi; Kunjungan[i]= false;
17
(Sambungan) for(i=0; i<JumlahVerteks; i++) { Posisi[i]= NilaiAcuan; Sebelum[i]= TakTerdefinisi; Kunjungan[i]= false; } Posisi[Awal]=0; for (Verteks =0; Verteks < JumlahVerteks; Verteks++) { var JarakTerpendek = NilaiAcuan; Berhenti = -1; for (i=0; i < JumlahVerteks; i++) { if (!Kunjungan[i]) { if (Posisi[i] <= JarakTerpendek) { JarakTerpendek = Posisi[i]; Berhenti = i; } } } Kunjungan[Berhenti] = true; for (i=0; i < JumlahVerteks; i++) { if (!Kunjungan[i]) { var w = bobot(Berhenti, i); if (Posisi[Berhenti]+w < Posisi[i]) { Posisi[i] = Posisi[Berhenti] + w; Sebelum[i] = Berhenti; } } } if (debug1) { doc.write("Iterasi ke [ " + Verteks+ " ]"); var n; n =Posisi.length; doc.write("
"); for (i=0; i" + i +"");
(Sambungan) n =Posisi.length; doc.write("
"); for (i=0; i" + i +""); } doc.write("
"); var fixnum; for (i=0; i" + fixnum +""); } doc.write("
"); for (i=0; i" + Sebelum[i] +""); } doc.write("
"); for (i=0; i" + Kunjungan[i] +""); } doc.write("
"); doc.write(" "); } } i=Akhir; }
Nilai Awal dan Akhir dari function dijkstra diperoleh dari inputan user pada option value, seperti pada contoh dibawah ini. User menginput data awal dan akhir yaitu Q-mart dan Santika, dimana nilai Q-Mart = 5 dan Santika = 6 (data tersebut sesuai urutan array). SElanjutnya fungsi ini akan melakukan looping pada graf sampai node tujuan ditemukan, adapun dalam melakukan looping fungsi ini
19
membentuk tiga buah variabel yang akan menjadi parameter fungsi lainnya. Variabel trersebut yaitu jarak, predecessor dan status kunjungan. Berikut gambaran hasil looping fungai dijkstra dapat dilihat pada gambar 4.23 berikut:
Gambar 4.23 Perhitungan Algoritma Dijkstra
4.1.5 Pengujian Sistem Pengujian sistem ini bertujuan untuk mengetahui apakah aplikasi yang dibangun sudah berjalan dengan baik. Untuk pengujian ini dilakukan pengujian
20
secara fungsional (alpha dan beta). Metode yang digunakan dalam pengujian ini adalah black box yang berfokus pada persyaratan fungsional dari aplikasi yang dibangun. Berikut ini adalah tabel rencana pengujian dari sistem yang dibangun: Tabel 4.3 Rencana Pengujian Kelas Uji Form Login
Menu Admin
Menu User
Butir Uji
Jenis Pengujian
Menampilkan, memvalidasi data input
Blackbox
Menampilkan menu admin
Blackbox
Menampilkan form tambah lokasi
Blackbox
Menampilkan form update lokasi
Blackbox
Menampilkan form hapus lokasi Menampilkan peta sebaran lokasi
Blackbox Blackbox
Menampilkan form kalkulasi jarak dan rute
Blackbox
Menampilkan peta rute yang akan dilalui
Blackbox
1) Pengujian Alpha Pengujian alpha jenis blackbox merupakan pengujian validasi yang menitik beratkan pada hasil output dari kendali input yang dimasukan pada form tampilan, dimana pengujian dikatakan berhasil apabila output sesuai dengan kendali input yang dimasukan pada tiap tampilan. Tahapan pengujian alpha dapat dilihat pada tabel di berikut:
21
a) Pengujian Memulai Sistem Tabel 4.4 Pengujian memulai sistem Kasus dan Hasil Uji Data masukan Memasukan alamat URL
Reaksi yang diharapkan Muncul tampilan utama Muncul menu utama user
Pengamatan Tampilan utama tampil halaman menu utama tampil
Kesimpulan Diterima Diterima
b) Pengujian Form Login Tabel 4.5 Pengujian form login Kasus dan Hasil Uji Data masukan Memasukan username dan password
Reaksi yang diharapkan Muncul halaman dan menu admin
Pengamatan Menu admin tampil
Kesimpulan Diterima
c) Pengujian Manipulasi Data Lokasi Tabel 4.6 Pengujian Manipulasi Data Lokasi Kasus dan Hasil Uji Data Reaksi yang masukan diharapkan Memilih menu Muncul tabel data Data Lokasi lokasi yang akan dimanipulasi Menginput Data apotik atau data apotik mall dan atau mall dan supermarket supermarket berhasil ditambahkan Mengubah Data apotik atau data apotik mall dan atau mall dan supermarket supermarket berhasil diubah
Pengamatan
Kesimpulan
Tabel data lokasi muncul
Diterima
Data apotik atau mall dan supermarket bertambah pada tabel masing-masing
Diterima
Data apotik atau mall dan supermarket berubah pada tabel masing-masing
Diterima
22
(sambungan) Menghapus data apotik atau mall dan supermarket
Data apotik atau mall dan supermarket berhasil di hapus
Data apotik atau mall dan supermarket terhapus pada tabel masing-masing
Diterima
d) Pengujian Informasi Sebaran Lokasi Tabel 4.7 Pengujian Informasi Sebaran Lokasi Kasus dan hasil uji Data Masukan Memilih menu lokasi Memilih menu map view Memilih menu satellite view Memilih menu Direction
Reaksi yang diharapkan Muncul Map sebaran lokasi Muncul Map data lokasi dalam bentuk map view Muncul Map data lokasi dalam bentuk satellite view Muncul menu Direction
Pengamatan Map sebaran lokasi tampil Map data lokasi dalam bentuk map view tampil Map data lokasi dalam bentuk satellite view tampil menu Direction tampil
Kesimpulan Diterima Diterima
Diterima
Diterima
e) Pengujian Fitur Kalkulasi Jarak Tabel 4.8 Pengujian Fitur Kalkulasi Jarak Kasus dan Hasil Uji Data Masukan Memilih lokasi awal dan lokasi tujuan Mengklik button Kalkulasi Jarak Mengklik button Show on Map
Reaksi yang diharapkan Muncul menu lokasi awal dan lokasi tujuan Muncul hasil kalkulasi jarak serta rute yang akan dilalui Muncul rute Map yang akan dilalui
Pengamatan
Kesimpulan
menu lokasi awal dan lokasi tujuan tampil
Diterima
Hasil kalkulasi jarak serta rute yang akan dilalui tampil
Diterima
Rute Map yang akan dilalui tampil
Diterima
23
2) Kesimpulan Pengujian Alpha Hasil uji dari pengujian alpha yang telah dilakukan, menunjukan bahwa aplikasi yang dibangun sudah memenuhi persyaratan fungsional, artinya secara fungsional sistem yang telah dibangun dapat menghasilkan keluaran yang diharapkan. 3) Pengujian Beta Pengujian beta dilakukan untuk menguji pada aplikasi browser, seperti yang ditunjukkan pada tabel di bawah ini: Tabel 4.9 Pengujian Sistem Pada Aplikasi Browser Jenis Aplikasi Browser
Form Login
Manipulasi Data Lokasi
Lihat Informasi Sebaran Lokasi
Kalkulasi Rute
Lihat Rute Map
Google Chrome
Berhasil
Berhasil
Berhasil
Berhasil
Berhasil
Firefox
Berhasil
Berhasil
Berhasil
Berhasil
Berhasil
Opera
Berhasil
Berhasil
Berhasil
Berhasil
Berhasil
Internet Exlporer
Berhasil
Berhasil
Berhasil
Tidak Berhasil
Tidak berhasil
a. Tampilan sistem pada browser google chrome
Gambar 4.24 Pengujian Sistem Pada Aplikasi Browser Google Chrome
24
b. Tampilan sistem pada browser firefox
Gambar 4.25 Pengujian Sistem Pada Aplikasi Browser Firefox c. Tampilan sistem pada browser opera
Gambar 4.26 Pengujian Sistem Pada Aplikasi Browser Opera
25
d. Tampilan sistem pada broser internet explorer
Gambar 4.27 Pengujian Sistem Pada Browser Internet Explorer 4) Kesimpulan Pengujian Beta Hasil dari pengujian beta yang telah dilakukan pada beberapa aplikasi browser menunjukan bahwa sistem berjalan dengan baik tanpa ada kesalahan atau error, kecuali pada aplikasi browser internet explorer, dimana pada tampilan kalkulasi rute, rute yang akan di kalkulasikan tidak tampil. 4.2 Pembahasan Kota Gorontalo merupakan salah satu daerah atau wilayah yang luas dan sedang berkembang yang memiliki banyak fasilitas umum terutama apotik, mall dan supermarket. Sebagai kota yang luas pastinya Kota Gorontalo memiliki sangat banyak jalur perjalanan yang tentu saja tidak mudah untuk mengetahui atau mengingat jalan–jalan atau rute perjalanan yang terletak di dalam kawasan Kota Gorontalo. Berdasarkan hasil penelitian yang telah dicapai, Sistem Informasi Geografis Menentukan Rute Terpendek ini dapat menjadi solusi dari permaslahan yang ada
26
sebelumnya. Sistem ini dapat menampilkan informasi mengenai titik lokasi fasilitas umum seperti apotik, mall dan supermarket. Infromasi yang dihasilkan berupa peta yang berisi titik-titik penyebaran lokasi apotik, mall dan supermarket, serta informasi mengenai rute terpendek dari lokasi awal menuju ke lokasi tujuan user dengan menggunakan algoritma dijkstra. Berikut adalah langkah-langkah penerapan algoritma dijkstra dari Q-Mart menuju ke Santika Dept. Store: - Pada awalnya status dari titik yang belum dipilih diinisialisasikan dengan false dan titik yang sudah dipilih diinisialisasi dengan true. - Tentukan jarak dari titik yang berhubungan langsung dengan titik awal yaitu titik 5 (Q-Mart), seperti dari titk 5 ke titik 0 = 1,3 km, dari titik 5 ke titik 3 = 2,2 km, dan dari titik 5 ke titik 4 = 2 km. Sedangkan untuk titik 1, 2, 6, 7 diinisialisasikan dengan „-„ karena tidak ada lintasan yang menghubungkan secara langsung dengan titik awal. - Predecessor (titik sumber) dari titik 5, 0, 3, 4 adalah titik 5, karena jarak dihitung dari titik 5 sehingga titik 5 disebut sebagai predecessor (titik sumber). Sedangkan untuk titik 1, 2, 6, 7 diinisialisasikan dengan „-„ karena tidak ada lintasan yang langsung menghubungkan dari titik sumber. Tabel 4.10 Hasil Iterasi ke-0 Titik Jarak Predecessor Status
0 1,3 5 False
1 False
2 False
3 2,2 5 False
27
4 2 5 False
5 0 True
6 False
7 False
- Dari tabel 4.10 pilih titik yang memiliki jarak paling kecil dan statusnya masih false yaitu titik 0. Untuk itu status dari titik 0 menjadi true dan predecessor-nya masih tetap 5. Sedangkan untuk titik yang lainnya predecessor-nya masih sama. Karena titik 0 sudah terpilih maka diperoleh titik 1 dengan jarak = 1,9 km dan titik 2 dengan jarak = 2 km, dan predecessor titik 1 dan 2 adalah 0, dimana untuk mencapai titik 1 dan 2 dari titik 5 harus melalui titik 0, sehingga diperoleh hasil seperti pada tabel 4.11 berikut: Tabel 4.11 Hasil Iterasi ke-1 Titik Jarak Predecessor Status
0 1,3 5 True
1 3,2 0 False
2 3,3 0 False
3 2,2 5 False
4 2 5 False
5 0 True
6 False
7 False
- Dari tabel 4.11 didapatkan bahwa titik 4 yang memiliki jarak paling kecil, sehingga statusnya akan berubah menjadi true dan predecessor-nya masih tetap titik 5, sehingga diperoleh hasil seperti pada tabel 4.12 berikut: Tabel 4.12 Hasil Iterasi ke-2 Titik Jarak Predecessor Status
0 1,3 5 True
1 3,2 0 False
2 3,3 0 False
3 2,2 5 False
4 2 5 True
5 0 True
6 False
7 False
- Dari tabel 4.12 didapatkan bahwa titik 3 yang memiliki jarak paling kecil, sehingga statusnya akan berubah menjadi true dan predecessor-nya masih tetap titik 5. Jika titik 3 terpilih, maka terjadi perubahan pada jarak titik 1 dan titik 2 dimana jarak pada titik 1 awalnya 3,2 menjadi 3,1 dan jarak pada titik 2 awalnya 3,3 menjadi 2,95. Jarak 3,1 dan 2,95 pada titik 1 dan titik 2 diperoleh dari jalur yang menghubungkan antara titik 5 ke titik 1 dan titik 5 ke titik 2 28
yaitu melewati titik 3 dengan jarak lebih pendek, sehingga predecessor titik 1 dan 2 menjadi titik 3. Karena titik 3 sudah terpilih maka diperoleh titik 7 dengan jarak 2,65 dan predecessor titik 7 yaitu titik 3. Sehingga diperoleh hasil seperti pada tabel 4.13 berikut: Tabel 4.13 Hasil Iterasi ke-3 Titik Jarak Predecessor Status
0 1,3 5 True
1 3,1 3 False
2 2,95 3 False
3 2,2 5 True
4 2 5 True
5 0 True
6 False
7 2,65 3 False
- Dari tabel 4.13 didapatkan titik 7 memiliki jarak yang paling kecil sehingga statusnya berubah menjadi true dan predecessor-nya masih sama. Sehingga diperoleh hasil seperti pada tabel 4.14 berikut: Tabel 4.14 Hasil Iterasi ke-4 Titik Jarak Predecessor Status
0 1,3 5 True
1 3,1 3 False
2 2,95 3 False
3 2,2 5 True
4 2 5 True
5 0 True
6 False
7 2,65 3 True
- Dari tabel 4.14 didapatkan titik 2 memiliki jarak paling kecil sehingga statusnya akan berubah menjadi true. Jika titik 2 sudah dipilih, maka diperoleh titik 6 yang bersumber dari titik 5 ke titik 3, lalu ke titik 2, kemudian ke titik 6 dengan jarak 3,09 dan predecessor-nya yaitu titik 2. Sehingga diperoleh hasil seperti pada tabel 4.15 berikut: Tabel 4.15 Hasil Iterasi ke-5 Titik Jarak Predecessor Status
0 1,3 5 True
1 3,1 3 False
2 2,95 3 True
3 2,2 5 True
29
4 2 5 True
5 0 True
6 3,09 2 False
7 2,65 3 True
- Dari tabel 4.15 didapatkan titik 6 memiliki jarak paling kecil sehingga statusnya berubah menjadi true dan predecessor-nya masih sama. Sehingga diperoleh hasil seperti pada tabel 4.16 berikut: Tabel 4.16 Hasil Iterasi ke-6 Titik Jarak Predecessor Status
0 1,3 5 True
1 3,1 3 False
2 2,95 3 True
3 2,2 5 True
4 2 5 True
5 0 True
6 3,09 2 True
7 2,65 3 True
- Dari tabel 4.16 dapat dilihat bahwa semua titik telah terpilih hanya tinggal titik 1 yang belum dipilih, selanjutnya titik 1 statusnya akan berubah true dan predecessor-nya masih tetap titik 3 dengan jarak 3,1. Sehingga diperoleh hasil seperti pada tabel 4.17 berikut: Tabel 4.17 Hasil Iterasi ke-6 Titik Jarak Predecessor Status
0 1,3 5 True
1 3,1 3 True
2 2,95 3 True
3 2,2 5 True
4 2 5 True
5 0 True
6 3,09 2 True
7 2,65 3 True
Untuk melihat jalur mana yang terpilih dapat ditelusuri dari predecessornya, sehingga akan didapatkan jalur tercepat dari titik 5 (Q-Mart) menuju ke titik 6 (Santika Dept. Store) yaitu
5
3
2
6dengan total jarak 3,09 km.
Gambar 4.28 Rute Tercepat dari Q-Mart ke Santika Dept. Store 30
Gambar 4.29 Perhitungan Algoritma Dijkstra Untuk pencarian rute terpendek ini sebelumnya telah dilakukan oleh Yuliawati (2009) dengan judul “Pencarian Jarak Terpendek Menggunakan Metode Breadth First Search Dan Metode Hill Climbing”. Penelitian ini menghasilkan simulasi perbandingan antara dua metode yang menjadi konsep dasar pencarian jarak yang bernilai minimum. Penelitian lainnya telah dilakukan oleh Indarti (2009) dengan judul “Pencarian Jarak Terpendek ke Suatu Tempat Dengan Menggunakan Metode
31
Heuristik Berbasis SMS”. Dalam penelitianannya Indarti membuat aplikasi pencarian jarak terpendek yang dapat menerima sms dari pengguna dengan format yang telah ditentukan, kemudian aplikasi akan menjalankan pencarian secara otomatis berdasarkan koordinat dari kota asal ke kota tujuan.
