BAB III
DESAIN PERANCANGAN
3.1 Algoritma Dijkstra
Sebelum menggunakan Algoritma dijkstra untuk menentukan rute
terpendek kita membutuhkan beberapa data seperti lokasi awal, lokasi akhir,
lokasi yang dapat dilewati, dan jarak antar lokasi. Setelah semua data itu
terkumpul maka algoritma Dijkstra dapat dilakukan. disini penulis akan menggunakan
algoritma Dijkstra untuk melakukan pencarian rute perjalanan terpendek untuk menuju
sentra grosir cikarang.
Berikut merupakan tahapan dalam penggunaan algoritma Dijkstra :
1.
Tentukan titik awal, dimana
titik tersebut akan menjadi node pertama pada sistem.
2.
Tentukan bobot (jarak) dari
setiap node ke node lainnya, kemudian set nilai 0 pada node pertama dan nilai
tak terhingga pada node lainnya (belum terisi). Dengan melakukan itu jika
programnya dijalankan maka algoritma Dijkstra akan mencari bobot terkecil dari
satu node ke node selanjutnya satu per satu.
3.
Setting semua node yang belum
dilalui sebagai “Belum dilewati” dan setting node awal sebagai “node
keberangkatan”.
4.
Pada node keberangkatan,
perhitungkan node tetangga yang belum
dilalui dan perhitungkan juga jarak dari awal keberangaktan. Jika jaraknya
lebih kecil dari jarak sebelumnya (yang telah diperhitungkan sebelumnya) hapus
data yang lama simpan ulang data jarak sebelumnya dengan data jarak yang lebih
pendek.
5.
Setelah selesai
mempertimbangkan setiap jarak terhadap node tetangga, tandai node yang telah
dilewati sebagai “Node dilewati”. Node dilewati tidak akan pernah dicek
kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal
bobotnya.
6. Set “Node belum dilewati”dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selanjutnya dan lanjutkan dengan kembali ke step 4.
3.2 Graf Algoritma Dijkstra
Berikut merupakan beberapa rute yang dapat ditempuh untuk menuju
sentra grosir cikarang. Dengan menggunakan bantuan Google Maps dapat diketahui jarak
tiap node yang telah dipilih,yang kemudian dapat dibuat garis dan diberi nilai
sebagai jarak untuk menghubungkan setiap node tersebut, Setelah dihubungkan
maka akan terbentuk sebuah graf seperti pada gambar dibawah :
Gambar 1. Tampilan rute pada Google map
Untuk
mempermudah pembacaan peta kami membuatkan graf yang telah disesuaikan dengan
posisi dan jarak tiap node pada Google map, seperti yang dapat dilihat pada
graf dibawah kami membedakan warna pada node H yang merupakan titik akhir untuk
mempermudah dalam pembacaan graf.
Gambar
2. Graf Algoritma Dijkstra
Berikut merupakan keterangan tiap nodenya :
Tabel 1. Keterangan tiap node
|
Node |
Keterangan |
|
A |
Sumberurip |
|
B |
Sumbersari |
|
C |
Karanghaur |
|
D |
Rengasdengklok |
|
E |
Karangpatri |
|
F |
Karangsari |
|
G |
Tanjungpura |
|
H |
Sentra Grosir Cikarang |
|
I |
Sukadarma |
Berikut adalah jarak antar lokasi (node) dalam satuan Kilometer:
Tabel 2. Jarak Antar Lokasi
|
Lokasi - lokasi lain |
Jarak (km) |
|
Sumberurip (A) – Sumbersari (B) |
3,6 |
|
Sumbersari (B) – Karanghaur (C) |
1 |
|
Sumbersari (B) – Rengasdengklok (D) |
3,7 |
|
Karanghaur (C) – Karangpatri (E) |
5,8 |
|
Karanghaur (C) – Tanjungpura (G) |
14 |
|
Rengasdengklok (D) – Tanjungpura (G) |
13,4 |
|
Karangpatri (E) - Sukadarma
(I) |
5 |
|
Karangpatri (E) - Karangsari
(F) |
10,9 |
|
Karangsari (F) - Tanjungpura (G) |
5,7 |
|
Karangsari (F) - Sentra Grosir Cikarang (H) |
8,2 |
|
Sentra Grosir Cikarang (H) - Sukadarma (I) |
11 |
BABIV
IMPLEMENTASI
4.1 Program
Setelah semua data itu
berhasil dikumpulkan dan programnya telah dibuat, disini kami akan melakukan
percobaan untuk mengetest algoritma dijkstra:
Pada percobaan ini kami
menggunakan node A (Sumberurip) sebagai titik awal dan node H (Sentra
Grosir Cikarang) sebagai titik akhir. Lalu mencari rute perjalanan terpendek
dengan menggunakan metode djikstra. Untuk programnya sendiri dapat dilihat pada
gambar dibawah ini:
Gambar 3. Screenshot
Program
Gambar 4. Screenshot Program 2
Gambar 5. Screenshot
Program 3
4.2 Hasil
Dari hasil program di atas
didapat rute perjalanan terpendek dari titik awal titik A (Sumberurip) ke titik
akhir titik H (Sentra Grosir Cikarang) yaitu :
‘A’ (Sumberurip) -> ‘B’ (Sumbersari) -> ‘C’ (Karanghaur) ->
‘E’ (Karangpatri) -> ‘I’ (Sukadarma) -> ‘H’ (Sentra Grosir Cikarang)
dengan panjang rutenya adalah 26,4 KM
Gambar 6. Screenshot Hasil Program
BABV
PENUTUP
5.1
Kesimpulan
Dengan begini perhitungan
jalur terpendek menggunakan Algoritma Dijktra dari Sumberurip menuju Sentra
grosir cikarang dinyatakan berhasil karena mendapatkan hasil yang akurat.
0 comments:
Posting Komentar