Definisi Algoritma Dijkstra
Algoritma dijkstra ditemukan oleh seorag
ilmuwan computer berkebangsaan Belanda, bernama Edsger Dijkstra. Pada dasarnya, algoritma ini
merupakan salah satu bentuk algoritma greedy. Algoritma
ini termasuk algoritma pencarian graf yang digunakan untuk menyelesaikan
masalah lintasan terpendek dengan satu sumber pada sebuah graf yang tidak
memiliki cost sisi negatif, dan menghasilkan sebuah pohon lintasan terpendek. Algoritma ini
sering digunakan pada routing. Algoritma dijkstra mencari
lintasan terpendek dalam sejumlah langkah. Algoritma ini menggunakan strategi greedy sebagai berikut :
Untuk
setiap simpul sumber(source) dalam graf, algortima ini
akan mencari jalur dengna cost minimum antara simpul tersebut dengan simpul lainnya. Algoritma juga dapat
digunakan untuk mencari total biaya(cost) dari
lintasan terpendek yang dibentuk dari sebuah simpul ke sebuah simpul tujuan.
Sebagai contoh, bila simpul pada graf merepresentasikan kota dan bobot sisi
merepresentasikan jarak antara 2 kota yang mengapitnya, maka algoritma dijkstra
dapat digunakan untuk mencari rute terpendek antara sebuah kota dengan kota
lainnya.
Skema Umum Algoritma Dijkstra
Berikut
adalah skema umum dari algoritma dijkstra pada pencarian shortest path :
1. Buatlah 3
buah list, yaitu list jarak(list 1), list simpul-simpul sebelumnya(list 2), dan
list simpul yang sudah dikunjungi(list 3), serta sebuah variable yang menampung
simpul saat ini(current vertex).
2. Isi semua
nilai dalam list jarak dengan tak hingga, kecuali simpul awal yang diisi
dengan0.
3. Isi semua
nilai dalam list 2 dengan false
4. Isi semua nilai dalam list 3 dengan null
5. Current Vertex diisi dengan simpul awal(start).
6. Tandai current vertex sebagai
simpul yang telah dikunjungi.
7. Update list 1 dan 2
berdasarkan simpul-simpul yang dapat langsung dicapai dari current vertex
8. Update current vertex dengan simpul yang
paling dekat dengan simpul awal.
9. Ulangi
langkah 6 sampai semua simpul sudah dikunjungi.
C. Metode Pencarian Jalur Terpendek
Algoritma
ini bertujuan untuk menemukan jalur terpendek berdasarkan bobot terkecil dari
satu titik ke titik lainnya. Misalkan titik mengambarkan gedung dan garis
menggambarkan jalan, maka algoritma Dijkstra melakukan kalkulasi terhadap semua
kemungkinan bobot terkecil dari setiap titik.
Pertama-tama
tentukan titik mana yang akan menjadi node awal, lalu beri bobot jarak pada
node pertama ke node terdekat satu per satu, Dijkstra akan melakukan
pengembangan pencarian dari satu titik ke titik lain dan ke titik selanjutnya
tahap demi tahap. Inilah urutan logika dari algoritma Dijkstra:
1.
Beri nilai
bobot (jarak) untuk setiap titik ke titik lainnya, lalu set nilai 0 pada node
awal dan nilai tak hingga 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 di cek
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.
Dibawah ini penjelasan langkah per
langkah pencarian jalur terpendek secara rinci dimulai dari node awal sampai
node tujuan dengan nilai jarak terkecil.
1. Node awal 1, Node tujuan 5. Setiap edge yang
terhubung antar node telah diberi nilai
Contoh
kasus Djikstra - Langkah 1
2. Dijkstra melakukan kalkulasi terhadap node
tetangga yang terhubung langsung dengan node keberangkatan (node 1), dan hasil
yang didapat adalah node 2 karena bobot nilai node 2 paling kecil dibandingkan
nilai pada node lain, nilai = 7 (0+7).
3. Node 2 diset menjadi node keberangkatan dan
ditandai sebagi node yang telah terjamah. Dijkstra melakukan kalkulasi kembali
terhadap node-node tetangga yang terhubung langsung dengan node yang telah
terjamah. Dan kalkulasi dijkstra menunjukan bahwa node 3 yang menjadi node
keberangkatan selanjutnya karena bobotnya yang paling kecil dari hasil kalkulasi
terakhir, nilai 9 (0+9).
4. Perhitungan berlanjut dengan node 3 ditandai
menjadi node yang telah terjamah. Dari semua node tetangga belum terjamah yang
terhubung langsung dengan node terjamah, node selanjutnya yang ditandai menjadi
node terjamah adalah node 6 karena nilai bobot yang terkecil, nilai 11 (9+2).
5. Node 6 menjadi node terjamah, dijkstra melakukan kalkulasi kembali, dan menemukan bahwa node 5 (node tujuan ) telah tercapai lewat node 6. Jalur terpendeknya adalah 1-3-6-5, dan niilai bobot yang didapat adalah 20 (11+9). Bila node tujuan telah tercapai maka kalkulasi dijkstra dinyatakan selesai.
Contoh kasus Djikstra - Langkah 5
No comments:
Post a Comment