Dijktra Algoritmasının temeli Hollandalı bilgisayar bilimcisi olan Edsger Dijkstra’ya dayanmaktadır. Edsger Dijkstra , 1959’da ağırlıklı bir grafiğe uygulanabilecek bir algoritma önerdi. Grafiğin her kenarında negatif olmayan bir değer içermesi şartıyla, grafik o yönde devam edebilir veya etmeyebilir. Bu algoritmaya “Dijkstra Algoritması” adını verdi. Dijkstra Algoritması, seçtiğiniz bir düğüm ile bir grafikteki diğer tüm düğümler arasındaki en kısa yolun hesaplanmasına olanak tanır.
Nasıl çalıştığı bir örnekle gösterilebilir. Bir kullanıcı A noktasından B noktasına gitmek istediğinde algoritma tüm rotaları tanımlamaya başlar. A düğümünden H düğümüne en kısa yoldan nasıl gidebiliriz inceleyelim.
- 1. Aşama
Başlangıç düğümü olarak A düğümünü seçelim.Başlangıçta diğer düğümlerin erişim imkanı olmadıgı için uzaklık değerlerine sonsuz değerini atarız. Durum aşağıdaki gibi olur.
| Durum | A | B | C | D | E | F | H |
| Başlangıç | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
- 2. Aşama
Başlangıç düğümünden başlayarak komşu olan düğümlerine olan uzaklıklarını durum tablomuzda gösteriyoruz ve en kısa olan yolun düğümünü seçerek bir sonraki düğüme geçiyoruz. Şeklimizde A düğümünün 3 düğüme komşuluğu bulunmaktadır ve en az maliyetli olan E düğümü seçiyoruz.
| Durum | A | B | C | D | E | F | H |
| Başlangıç | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| A | 5 | 6 | ∞ | 1 | ∞ | ∞ |
- 3. Aşama
E düğümünün C düğümüne komşuluğu bulunmakta. C düğümünün yeni değeri 1+2=3 oldu.C değerine E üzerinden gitmek daha az maliyetli olduğu için C değeri üzerinde güncelleme yaptık. Bir sonraki düğüme geçmek için en küçük değere sahip ve daha önceden ziyaret edilmemiş olan C’den devam edelim.
| Durum | A | B | C | D | E | F | H |
| Başlangıç | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| A | 5 | 6 | ∞ | 1 | ∞ | ∞ | |
| E(1) | 5 | 3 | ∞ | ∞ | ∞ |
- 4. Aşama
C’den B ve D düğümlerine komşuluk bulunmakta. B nin yeni değeri 3+1=4<5 olduğu için B düğümün değerini güncelliyoruz. D’nin yeni degeri 3+4=7 oldu. Durum tablosunda B düğümünün degeri en düşük olduğu için B düğümünden devam ediyoruz.
| Durum | A | B | C | D | E | F | H |
| Başlangıç | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| A | 5 | 6 | ∞ | 1 | ∞ | ∞ | |
| E(1) | 5 | 3 | ∞ | ∞ | ∞ | ||
| C(3) | 4 | 7 | ∞ | ∞ |
- 5. Aşama
B düğümünün F düğümüne komşuluğu bulunmakta ve 4+1=5 den F nin yeni değerini güncelliyoruz.
| Durum | A | B | C | D | E | F | H |
| Başlangıç | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| A | 5 | 6 | ∞ | 1 | ∞ | ∞ | |
| E(1) | 5 | 3 | ∞ | ∞ | ∞ | ||
| C(3) | 4 | 7 | ∞ | ∞ | |||
| B(4) | 1 | ∞ |
- 6. Aşama
F düğümü D ve H düğümüne komşuluğu bulunmakta. H düğümünün değeri 5+2=7 oldu. D düğümünün degeri 7 iken 5+3=8 olması gerekmekteydi ama 8>7 olduğundan mevcut değerini korudu.
| Durum | A | B | C | D | E | F | H |
| Başlangıç | 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ |
| A | 5 | 6 | ∞ | 1 | ∞ | ∞ | |
| E(1) | 5 | 3 | ∞ | ∞ | ∞ | ||
| C(3) | 4 | 7 | ∞ | ∞ | |||
| B(4) | 1 | ∞ | |||||
| F(5) | 7 | 7 |
Sonuç;
Tüm düğümleri gezdiğimize göre A düğümünden H düğümüne en kısa yol A->E->C->B->F->H şeklindedir. Maliyeti ise 1+2+1+1+2=7’dir.
