Dijkstra Algoritması

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.

Dijkstra Algorithm
  • 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.

DurumABCDEFH
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.

DurumABCDEFH
Başlangıç0
A561
  • 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.

DurumABCDEFH
Başlangıç0
A561
E(1) 53 
  • 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.

DurumABCDEFH
Başlangıç0
A561
E(1) 53 
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.

DurumABCDEFH
Başlangıç0
A561
E(1) 53 
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.

DurumABCDEFH
Başlangıç0
A561
E(1) 53 
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.

Dijkstra Algorithm

Yorum Yap:

E-posta hesabınız yayımlanmayacak.

Site Footer

Sliding Sidebar