Algoritma Dijkstra
Menemukan jalan termurah dari awal ke tujuan. Selalu mengambil tempat termurah yang menunggu di antrean prioritas, sehingga biaya menyebar dari awal seperti banjir.
- waktu O((V + E) log V)
- memori O(V)
- memakai antrean prioritas
Apa artinya?
- Biaya: harga sebuah langkah. Di labirin, tanah berbiaya 1, lumpur 3, dan air 9; di graf, angka pada sisi.
- Antrean prioritas: antrean tempat yang termurah maju duluan, bukan yang datang duluan.
- Perkiraan (h): tebakan biaya yang tersisa. A* hanya tetap tepat jika tebakan itu tidak pernah terlalu tinggi.
- Relaksasi sisi: memeriksa apakah lewat tempat saat ini memberi tetangga biaya lebih rendah, lalu mengambilnya jika ya.
- dalam antrean
- saat ini
- tuntas
- jalan termurah
- tanah · 1
- lumpur · 3
- air · 9
- dinding
Baru: Mulai di A1 dengan biaya 0. Satu-satunya di antrean.
Spasi: putar atau jeda. Panah kiri dan kanan: melangkah. Home dan End: lompat.
Coba ini: Pilih rawa. Jalan termurah memutari seluruh lumpur: dua kali lebih banyak langkah daripada garis lurus, tapi tetap lebih murah (34 lawan 36).
Cara kerjanya
Setiap tempat mendapat biaya: 0 untuk awal, tak hingga untuk sisanya. Dijkstra menyimpan tempat yang sudah dicapai dalam antrean prioritas dan selalu mengambil yang termurah. Biayanya lalu sudah pasti, karena jalan lain ke sana harus melewati sesuatu yang setidaknya sama mahal. Lalu ia melihat setiap tetangga: jika lewat tempat yang baru diambil lebih murah daripada biaya tetangga sejauh ini, tetangga mendapat biaya baru dan mengingat dari mana ia datang. Saat tujuan diambil, catatan itu menuntun kembali lewat jalan termurah.
Kapan ini pilihan yang tepat
Gunakan Dijkstra saat langkah punya biaya berbeda dan tidak ada yang kurang dari nol: peta jalan dan navigasi, perutean jaringan, sambungan penerbangan termurah. Jika setiap langkah berbiaya sama, BFS memberi jawaban yang sama dengan lebih sederhana. Dengan biaya negatif Dijkstra bisa keliru; untuk itu ada Bellman–Ford.