Dijkstra Algoritması

Dijkstra Algoritması Nedir?

Sevgi Paylaş
  •  
  •  
  • 2
  • 1
  •  
  •  
  •  
  • 1
  •  
  •  

Dijkstra algoritması Edsger Dijkstra tarafından oluşturulmuş ve günümüz Google Haritaların temellerini oluşturan devrimsel nitelikte bir algoritmadır.

Edsger Wybe Dijkstra Hollandalı matematikçi ve bilgisayar bilimcidir. Bu adamın geliştirdiği bu algoritma sayesinde navigasyonumuzu açıp en kısa yola ulaşabiliyoruz. Algoritmayı öğrendiğinizde harita dışında farklı işlerde de kullabilirsiniz. Temelde en kısa yolu bulmaya odaklanmış bir algoritmadır.

Edsger W. Dijkstra

Algoritmanın Çalışma Prensibi

Örneğin aşağıdaki şekli (graph) ele alalım. A noktasından başlayıp E noktasına varalım ve algoritma bize en kısa yolu söylesin.

Dijkstra Algoritması Örnek

A düğümünden (node) başlayalım. Henüz yolun başında olduğumuz için diğer düğümlere sonsuz ( ¥ ) değeri atıyoruz. Yani en başta her şey sonsuz. B, C, D, E, F hepsinin değeri sonsuzdur.

Hemen ardından A’nın komşularına bakılır. A’dan B’ye 2 değerinde gidiliyorsa B’nin değeri 2 olur. Aynı durumda C’nin değeri 1’dir.

Dijkstra Algoritması Kodu

Şimdi geldiğimiz komşularında komşularına bakacağız. Sırayla bakmak gerekirse B’ye gelirsek yeni komşularımız F ve E olur. O zaman F’nin değeri 7’dir. Aynı şekilde E’nin değeri ise 4’tür. F ve E’nin değerini bulurken bir önceki değerle toplarız. 2+5=F, 2+2=E

Dijkstra Algoritması C++

B’nin komşularını bulduğumuza göre şimdi C’nin komşularını bulacağız. C’nin komşuları F ve D’dir. O zaman 1+1=D, 1+2=F değerini verir. Buna göre D=2 değerindedir, F=3 değerindedir.

Dijkstra Algorithm Java

Daha önce F’ye uğramıştık. Bu yüzden önceki gidişimizdeki değer ile şuan ki değer kıyaslanır. Yeni aldığımız F=3 değeri, F=7 değerinden küçükse o yoldan devam edilir. Buna göre yeni gideceğimiz yer en kısa değere sahip olan yerdir yani D.

Bundan sonraki aşamada D’nin komşuları güncellenmeyecektir. Çünkü başka komşusu kalmamıştır. F’ye geri dönüp B’den E’ye geçmesi cidden işsizliktir. Algoritma gereksiz olduğunu bildiği için bu işlemi yapmaz.

F için 2 + 5 = 7 > 3

E için 2 + 7 = 9 > 4

Bir sonraki düğüm F’dir.

Dijkstra Algorithm

F’nin başka komşusu kalmadığı için son olarak E’yi denetliyor.

Dijkstra Algoritması Nedir

En sonunda bitişe geldiğimiz için hiç bir değişiklik olmayacaktır. Bu durumda en kısa yol 4’tür. A’dan B’ye oradan E’ye.

Algoritmanın eksi yanlarına bakacak olursa eksi (-) sayılar işin içine girince algoritmanın kafasını yanıyor. Çünkü her eksiye geldiğinde daha iyi bir yer var mı diye kontrol edeceğinden bir kısır döngüye girecektir. Bu da bizim hoşumuza gitmeyen bir etmen.

  • Bu Makale Hakkında Sen Neler Düşünüyorsun?

    E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir