Algoritma Dijkstra adalah algoritma yang digunakan untuk menemukan jalur terpendek dari satu simpul ke semua simpul lainnya dalam grafik berbobot positif. Algoritma ini dinamai dari matematikawan Edsger W. Dijkstra dan banyak digunakan dalam berbagai aplikasi seperti perutean dalam jaringan komputer, sistem transportasi, optimasi rute, dan masalah lain yang melibatkan mencari jarak terpendek.
Berikut adalah langkah-langkah umum untuk mengimplementasikan algoritma Dijkstra:
- Inisialisasi grafik:
- Tetapkan nilai jarak tak hingga (biasanya digunakan nilai besar seperti INF) ke semua simpul kecuali simpul awal.
- Tetapkan nilai jarak nol ke simpul awal.
- Tandai simpul awal sebagai simpul saat ini.
- Untuk simpul saat ini, hitung jarak terpendek ke semua tetangganya:
- Periksa tetangga-tetangga simpul saat ini.
- Jika jarak dari simpul awal ke simpul saat ini ditambah bobot sisi ke tetangga lebih kecil dari jarak saat ini ke tetangga, perbarui nilai jarak tetangga dengan nilai yang lebih kecil.
- Lakukan ini untuk semua tetangga simpul saat ini.
- Setelah menghitung semua tetangga simpul saat ini, tandai simpul saat ini sebagai “dikunjungi.”
- Pilih simpul dengan jarak terpendek yang belum dikunjungi sebagai simpul berikutnya.
- Ulangi langkah 3 hingga semua simpul telah dikunjungi atau sampai simpul tujuan tercapai.
- Setelah selesai, jalur terpendek dari simpul awal ke setiap simpul lainnya dapat ditentukan dengan melihat nilai jarak yang dihitung selama proses ini.
Algoritma Dijkstra menggunakan pendekatan “greedy” di mana selalu memilih simpul dengan jarak terpendek pada setiap langkah. Meskipun algoritma ini bekerja dengan baik untuk grafik berbobot positif, perlu dicatat bahwa jika terdapat bobot negatif pada grafik, maka algoritma Dijkstra tidak akan memberikan hasil yang benar. Untuk grafik yang mengandung bobot negatif, algoritma lain seperti Algoritma Bellman-Ford dapat digunakan.
Dalam aplikasi praktis, algoritma Dijkstra sering digunakan dalam aplikasi navigasi, seperti aplikasi peta dan navigasi GPS, untuk menemukan rute terpendek antara dua lokasi. Juga, dalam jaringan komputer, algoritma ini dapat digunakan untuk menemukan rute terpendek antara dua perangkat dalam jaringan berbobot.
Baca Juga :