Dijkstra algoritması
Başlangıçtan hedefe en ucuz yolu bulur. Öncelikli kuyrukta bekleyen en ucuz yeri her zaman önce alır, bu yüzden maliyetler başlangıçtan bir sel gibi yayılır.
- süre O((V + E) log V)
- bellek O(V)
- öncelikli kuyruk kullanır
Bunlar ne demek?
- Maliyet: bir hamlenin bedeli. Labirentte toprak 1, çamur 3, su 9 tutar; grafta kenardaki sayıdır.
- Öncelikli kuyruk: ilk gelenin değil, en ucuzun önce geçtiği bir kuyruk.
- Tahmin (h): kalan maliyet hakkında bir tahmin. A* ancak tahmin hiç fazla olmazsa kesin kalır.
- Kenar gevşetme: mevcut yerden geçmenin bir komşuya daha düşük maliyet verip vermediğine bakmak ve veriyorsa onu almak.
- kuyrukta
- şimdiki
- bitti
- en ucuz yol
- toprak · 1
- çamur · 3
- su · 9
- duvar
Yeni: Başlangıç A1, maliyet 0. Kuyruktaki tek eleman.
Boşluk: oynat veya duraklat. Sol ve sağ oklar: adım adım. Home ve End: atla.
Şunu deneyin: Bataklığı seçin. En ucuz yol çamurun tamamen etrafından dolaşır: düz çizginin iki katı hamle, yine de daha ucuz (36'ya karşı 34).
Nasıl çalışır
Her yer bir maliyet alır: başlangıç 0, geri kalanı sonsuz. Dijkstra ulaştığı yerleri öncelikli kuyrukta tutar ve her zaman en ucuzunu alır. O maliyet artık kesindir, çünkü oraya giden başka her yol en az onun kadar pahalı bir yerden geçmek zorundadır. Sonra her komşuya bakar: az önce aldığı yerden geçmek, komşunun şimdiki maliyetinden ucuzsa komşu yeni maliyeti alır ve nereden geldiğini hatırlar. Hedef alındığında bu kayıtlar en ucuz yoldan geriye götürür.
Ne zaman iyi bir seçimdir
Hamlelerin maliyeti farklı olduğunda ve hiçbiri sıfırdan az olmadığında Dijkstra kullanın: yol haritaları ve navigasyon, ağ yönlendirme, en ucuz uçuş aktarması. Her hamle aynı maliyetteyse BFS aynı cevabı daha basit verir. Negatif maliyetlerde Dijkstra yanılabilir; onlar için Bellman–Ford vardır.