Dijkstra ve Bellman Ford Algoritmaları

Dijkstra Algoritması

Algoritma kendisini literatüre kazandıran kişinin ismini taşıyor.Bilgisayar bilimlerinde en kısa yolu bulmak için kullanılan bu algoritma günümüzde pek çok yerde kullanılmamasına rağmen sektörde önemli firmalar tarafından birkaç yapay zeka uygulamasında kullanılmaktadır.

Genellikle algoritmalar graf üzerinde anlatılır.Bizde bu jargonu bozmamak amacıyla bir graf üzerinden algoritmayı anlatmaya çalışalım.

Yandaki fotoğrafta görüldüğü üzere graf üzerinden hareket edersek dijkstra algoritması herhangi bir düğümden diğer bütün düğümlere giden en kısa yolu hesaplar.Burada başlangıç düğümü olarak A düğümünü ele alalım. Başlangıçta bütün düğümlere erişimi olmadığını kabul ederek diğer düğümlerin maliyetini sonsuz olarak kabul ediyoruz.Başlangıç noktasınada sıfır maliyetini veriyoruz.Kısacası başlangıç durumunda herhangi bir düğüme gidemiyoruz.

Devam edecek olursak başlangıç olarak kabul ettiğimiz A düğümüne komsu olan bütün düğümlerin dolaşılmasını sağlayacağız ve bu düğümlerin ulaşım maliyeti hesaplanır.A düğümünün C düğümüne olan maliyeti 1 B düğümüne olan ulaşım maliyeti 2 dir.

Ardından B ve C düğümlerini işlemcideki process mantığı ile düşünecek olursak C kendini root düğüm olarak kabul eder.Aynı senaryo B düğümü içinde geçerlidir.

Özelicek olursak a düğümünün komşusu olan B ve C güncellendiler bir sonraki adımda da bu düğümlerin komşuları güncellendi bu aşamada istediğiniz düğümden hareket edebilirsiniz.Biz önce B düğümün komşularını daha sonra C düğümün komşularını güncelleyelim.Bu durumda E ve F düğümleri güncellenmiş olacaktır.Bu düğümlere ulaşım maliyeti ise E düğümü için 2 +5 = 7 F düğümü için 2+2=4 değerlerini elde ederiz.Daha sonra C düğümünü güncelleyelim.C düğümünün komşusu olan D ve F düğümleri önce F düğümü daha önce güncellemiştik ve değer olarak ulaşım maliyeti 7 çıkmıştı ancak yeni gelen değer,F için C üzerinden 1+2=3 olacak ve bu değer daha önceden hesaplanan 7 değerinden düşük olduğu için 7 yi 3 olarak güncellenir.Devam edecek olursak bu sefer D düğümün komşularını güncelleyelim. Burada dikkat edecek olursak D düğümün hiçbir komşusunu güncelleyemiyoruz çünlü mevcut değerlerden daha yüksek ulaşım maliyetleri mevcut F için 2+5=7 > 3 E için 2+7=9>4 diğer adımdaki düğümünde F düğümü olduğunu kabul edelim.F düğümün komşularında da aynı senaryodan ötürü bir değişiklik olmuyor son olarak e düğümünü ele aldığımızda komşusu olmadığı için grafımız kararlı bir halde bırakılıyor.

Düğümleri yol maliyetlerini hesaplayarak en kısa yoldan E düğümüne gidecek olan biri ilk olarak A ⇒ B ⇒ C ⇒ D ⇒ C ⇒ F ⇒ ⇒ D || B ⇒ E düğümüne ulaşmış oluruz.

_{Dijkstra Algoritması Dezavantajları}

_{Algoritma – değer taşıyan kenarlı graflarda maalesef doğru çalışmaz.Sebebi ise – değerdeki kenarın sürekli olarak mevcut daha iyi bir sonuç üretmesi ve algoritmayı hiçbir şekilde kararlı hale getirememesidir.}

Bellman Ford Algoritması

^{Bu algoritma kaynak ve hedef bazlı olarak çalışmakta aynı Dijkstra algoritmasında olduğu gibi gidecelek düğümler arasında en kısa yolu bulma amacıyla tasarlanmıştır. Bu anlamda, literatürde en kısa yol bulma algoritması (shortest path algorithm) olarak sınıflandırılabilir. Algoritma ağırlıklı şekiller (weighted graph) üzerinde çalışır. Kabaca, bütün düğümler için bütün kenarları dolaşır. Dolayısıyla performansı düğüm sayı ile kenar sayısının çarpımı olarak düşünülebilir. O( V E ) (Karmaşıklık= düğüm sayısı(vertex) * Kenar Sayısı (E) )}

^{Başlangıçta Dijkstra olduğu gibi bütün düğümlere sonsuz mesafesi atılır her düğüm ve kenar için düğümün üzerindeki yol maliyetinden daha küçük bir maliyet ile o düğüme ulaşılabilecek bir düğüm bulunduysa düğümü güncelliyoruz.}

^{Günümüzde popüler bir algoritmadır.Genellikle yapay zeka algoritmalarındaki datasetler fazla olduğu için algoritmada buffer sistemi ile tasarlanmış örnekleri mevcuttur.Bu bağlamda algoritma hızı ve karmaşıklığını azaltmak amacı ile gidilen düğümleri bufferda tutabiliriz. Iç içe iki döngü üzerine kurgulanan algoritma kenar ve düğüm sayısı kadar çalışmaktadır.Dijkstra ise kararlı olana kadar çalışırdı bu bellman ford’un Dijkstra olan avantajını gösterir ve ayrıca dijkstra daki negatif yol maliyeti sorunu ile kaynaklanan sonsuz döngü sorunu burada gidilen düğümlerin tutulmasıyla çözülmüştür.Algoritma Dijkstra algoritmasında olduğu gibi en küçük değere sahip olan kenardan gitmek yerine bütün graf üzerindeki kenarları test eder. Bu sayede aç gözlü yaklaşımının (greedy approach) handikapına düşmez ve her düğüme sadece bir kere bakarak en kısa yolu bulmuş olur.}

^{Yandaki görseldeki grafı tekrar ele alalım, öncelikle düğümlere değer ataması yapılır.İlk adımda sonsuz değerler atanıyordu.}

^{Daha sonra başlangıç düğünümüzün a hedef düğünümüzün ise E olduğunu varsayarak başlangıç düğümüne 0 değerini atalım.Burada rastgele olarak bir kural belirlememiz gerekiyor kural da denmez tabi düğümleri dolaşmak için rastgele bir yapı oluşturmamız gerekiyor.Ben alfabetik olarak dolaşmak istiyorum.}

^{Düğüm sıramız ⇒ A,B,C,D,E,F}

_{Bellman-Ford algoritması işte bu kenarları teker teker dolaşması itibariyle dijkstra dan ayrılır. Sırayla yukarıdaki kenarları (Edges) dolaşır ve graftaki değerleri günceller.}

_{Algoritma öncelikli olarak düğümleri dolaşıyor ve her düğüm için kenarları dolaşacak.}

_{A düğümü için kenarları dolaşıyoruz. Kenarlardan sadece AB ve AC kenarları, A düğümü ile ilgili. Aslında bütün kenarlar dolaşılıyor olmasına rağmen, sadece bu iki kenar, graftaki sonucu etkileyecek.}

_{AB 2, min(A,B) = 0 ⇒ 0+ 2 = 2}

_{AC 1, min(A,C) = 0 => 0+1 = 1}

_{Ardından B düğümüne geçiyoruz. Ve bu düğüm için bütün kenarları tekrar dolaşmaya başlıyoruz.}

_{Bu durumda etkisi görülecek kenarlar:}

_{Kenarlarıdır çünkü bunlar dışındaki kenarların bağladıkları düğümler sonsuz değerindedir ve güncelleme olmaz. Diğer bir deyişle grafın yukarıdaki şekilde, A,B,C düğümlerinde sonsuz dışında değerler bulunuyor .O halde sadece bu düğümlere komşu olan kenarları almak yeterlidir.}

_{BE 2, min (B,E ) 2, => 2 + 2 = 4}

_{BF 5, min(B,F) = 2 => 2+5 = 7}

_{CF 2, min (C,F) = 1 => 1+2 = 3, bu değer 7’den küçük olduğu için güncelliyoruz:}

_{CD -1, min(C,D) = 1=> 1+(-1) = 0}

_{Yukarıdaki son halimizde henüz 2 düğüm için işlem yapıldı ( A ve B düğümleri).Graf 2 düğüm için kararlı hale ulaşmıştır ve diğer düğümler için işlem devam etse bile graftaki değerler değişmez.}