Yazan : Şadi Evren ŞEKER
Bilgisayar bilimlerinde kullanılan ve algoritmayı literatüre kazandıran kişinin ismini taşıyan dijkstra algoritması, verilen bir şekilde (graph) en kısa yolu (shortest path) bulmak için kullanılır.
Bu algoritmanın çalışmasını örnek bir şekil( graph ) üzerinden göstermeye çalışalım. Bu gösterimin ardından Dijkstra algoritmasının başarısını ve zafiyetlerini tartışabiliriz.
[flashvideo file=http://www.bilgisayarkavramlari.com/wp-content/uploads/dijkstra.flv /]
Örnek olarak yukarıda bulunan şekli ele alalım. Dijkstra algoritması herhangi bir şekildeki bir düğümden diğer bütün düğümlere giden en kısa yolu hesaplar.
Örneğimizde başlangıç düğümü (node) olarak A düğümünü seçtiğimizi düşünelim ve algoritmanın çalışmasını bu düğümden başlayarak gösterelim.
Algoritma başlangıçta bütün düğümlere henüz erişim olmadığını kabul ederek sonsuz (¥ ) değeri atar. Yani başlangıç durumunda henüz hiçbir düğüme gidemiyoruz.
Ardından başlangıç düğümünün komşusu olan bütün düğümleri dolaşarak bu düğümlere ulaşım mesafesini günceller.
Bu güncelleme işleminden sonra güncellenen düğümlerin komşularını günceller ve bütün düğümler güncellenene ve şekil üzerinde yeni bir güncelleme olmayana kadar bu işlem devam eder.
Örneğin yukarıda A düğümünün komşusu olan düğümler (B ve C) güncellendiler. Bir sonraki adımda bu düğümlerin komşuları güncellenecektir. İstediğimiz bir düğüm ile başlayalım. Örneğin önce B sonra C düğümünün komşularını güncelleyelim:
Yukarıdaki şekilde, B düğümünün komşusu olan E ve F düğümleri güncellenmiştir. Bu güncelleme işlemi sırasında B düğümünün üzerindeki mevcut maliyet ile E ve F düğümlerine gidişten doğan maliyet toplanmıştır.
Örneğin E düğümü için 2 + 5 = 7 ve F düğümü için 2 + 2 = 4 değerleri bulunmuştur.
Şimdi bir sonraki düğüm olan C düğümünden güncelleme yapalım:
Bu aşamada güncellenen düğümler, C düğümünün komşusu olan D ve F düğümleridir. Bu düğümlerden, F düğümü daha önce güncellenmişti ve değer olarak 7 taşımaktaydı, ancak yeni gelen değer, F için C üzerinden 1 + 2 = 3 olarak hesaplanmış ve bu değer daha önceden hesaplanan 7 değerinden düşük olduğu için 7’nin üzerine yazılarak 3 olmuştur.
Algoritmanın çalışmasını sonraki düğümlerin güncellenmesi ile sürdürelim. Bu sefer örneğin D düğümünün komşularını güncelleyelim ( şu anda D, F ve E düğümleri aynı derecede yeni güncellenmiştir bunlardan herhangi birisi ile başlanması Dijkstra algoritmasına uygundur. Ancak recursive (özyineli) bir kodlama yapılıyorsa koda göre elbette yakın olan komşular güncellenecektir)
D düğümünün hiçbir komşusu güncellenmemiştir bunun sebebi hesaplanan değerlerin mevcut değerlerden yüksek olması ve dolayısıyla daha iyi bir sonuç bulunamamasıdır.
F için 2 + 5 = 7 > 3
E için 2 + 7 = 9 > 4
Dolayısıyla bir sonraki düğümü seçerek devam ediyoruz
F düğümünün komşularında da bir değişiklik olmuyor ve son olarak E düğümü deneniyor:
Son halimizde de bir değişiklik olmayarak şeklimiz (graph) kararlı bir halde ( daha fazla değişiklik olmadığı için) dolaşılmış ve bitmiş oluyor.
Yukarıdaki bu grafta, düğümler üzerinde yazılı olan değerler, A düğümünden başlanarak her düğüme gidilebilen en kısa yol mesafesini vermektedir. Örneğin şekildeki F düğümüne ulaşma maliyeti 3 olarak hesaplanmıştır ve Dijkstra algoritması, A düğümünden F düğümüne daha kısa bir yol bulunamayacağını iddia eder ( eşit farklı yollar bulunabilir ama en kısa yol yine de 3 olur)
Dijkstra algoritmasının zayıf yönü
Algoritma ne yazık ki eksi (-) değer taşıyan bir kenar bulunması halinde başarılı çalışmaz. Bunun sebebi eksi (-) değerdeki kenarın sürekli olarak mevcut durumdan daha iyi bir sonuç üretmesi ve algoritmanın hiçbir zaman için kararlı hale gelememesidir.
Örneğin aşağıdaki basit şekli ele alalım:
Yukarıdaki bu şekilde B-C kenarı (edge) -2 değerinde verilmiştir. Bu durumda A düğümünden başlayarak en kısa yolları hesaplamak istersek, öncelikli olarak A düğümünden komşusu olan düğümlere güncelleme yapılacaktır:
Ardından bu düğümlerin komşuları güncellenecektir. İki düğümde birbirine -2 değerini ekleyerek daha kısa bir yol bulacak ve birbirlerini güncelleyerek daha kısa sonuçlara ulaşacaktır.
Bu işlem ne yazık ki sonsuza kadar giden bir sürecin başlangıcıdır ve hiçbir zaman daha iyi bir sonuç bulma işlemi bitmez.
Sürekli olarak mevcut durumdan daha iyi bir durum bulunacak ve daha küçük değerler güncellenecektir. Bu yüzden Dijkstra algoritması, eksi (-) değer taşıyan şekillerde (graph) başarılı çalışmaz.