Algoritma Dijkstra (dinamai menurut penemunya, seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritma rakus (greedy algorithm) yang dipakai dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot sisi (edge weights) yang bernilai tak-negatif.
Saat ini sudah banyak algoritma yang bisa digunakan untuk menemukan
pencarian rute terpendek, dan tidak bisa di pungkiri Djikstra masih
menjadi salah satu yang populer dari sekian banyak algoritma tersebut.
Pada postingan kali ini kita akan membahas mendetail mulai dari apa itu
algoritma djikstra dan dan bagaimana cara kerja algoritma djikstra.
Edsger Djikstra
Djikstra merupakan salah satu varian bentuk algoritma popular dalam
pemecahan persoalan terkait masalah optimasi pencarian lintasan
terpendek sebuah lintasan yang mempunyai panjang minimum dari verteks a
ke z dalam graph berbobot, bobot tersebut adalah bilangan positif jadi
tidak dapat dilalui oleh node negatif. Namun jika terjadi demikian, maka
penyelesaian yang diberikan adalah infiniti (Tak Hingga). Pada
algoritma Dijkstra, node digunakan karena algoritma Dijkstra menggunakan
graph berarah untuk penentuan rute listasan terpendek. Berikut Pseudo
Code dan Flowchart Algoritma Djikstra:
Pertama-tama tentukan titik mana yang akan menjadikan node awal, lalu beri bobot jarak pada node pertama ke node terdekat satu persatu, Dijkstra akan melakukan pengembangan pencarian dari satu titik ke titik lain dan ke titik selanjutnya tahap demi tahap inilah urutan logika dari algoritma Dijkstra :
- 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)
- Set semua node “Belum Terjamah” dan set node awal sebagai “Node keberangkatan”
- Dari no 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.
- 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.
- Set “Node belum terjamah” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selajutnya dan lanjutkan dengan kembali ke step 3
Note : Bahkan menurut Andrew Goldberg, peneliti utama di Microsoft Research Silicon Valley, mengatakan ada banyak alasan mengapa peneliti terus mempelajari masalah pencarian jalan terpendek.
“Jalan terpendek adalah masalah optimasi yang relevan untuk berbagai macam aplikasi, seperti jaringan routing, game, desain sirkuit, dan pemetaan,” – Goldberg. “Industri selalu datang dengan aplikasi baru sepanjang waktu, membuat parameter yang berbeda untuk tiap masalah.
Teknologi dengan lebih banyak kecepatan dan kapasitas memungkinkan kita untuk memecahkan masalah yang lebih besar, sehingga dalam lingkup masalah jalan terpendek maka akan selalu ada optimasi.
Semoga Bermanfaat !
Daftar Pustaka
