UAYRI!: Bu yazıda hatalar bulunmaktadır (Uğur Bey’e teşekkürler). Bu yazıda anlatılan algoritma verilen örnekteki özel olarak sıralanmış kenarlar için doğru çalışmakta ancak farklı durumlarda hata yapabilmektedir. Bellman-Ford algoritmasının tam ve doğru anlatımı için http://www.bilgisayarkavramlari.com/2010/08/05/bellman-ford-algoritmasi-2/ adresindeki yazıyı okuyabilirsiniz.

Yazan : Şadi Evren ŞEKER

Bu algoritmanın amacı, bir şekil (graph) üzerindeki, bir kaynaktan (source) bir hedefe(target veya sink) giden en kısa yolu bulmaktır. Algoritma ağırlıklı şekiller (weighted graph) üzerinde çalışır ve bir anlamda Dijkstra algoritmasının iyileştirilmişi olarak düşünülebilir.

Algoritma aslında Dijkstra algoritmasından daha kötü bir performansa sahiptir ancak graftaki ağırlıkların eksi olması durumunda Dijkstra’nın tersine başarılı çalışı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) handikabına düşmez ve her düğüme sadece bir kere bakarak en kısa yolu bulmuş olur.

Algoritmanın çalışmasını yukarıdaki gibi eksi değerlere sahip bir şekil üzerinden anlamaya çalışalım.

Öncelikle düğümlere değer ataması yapılıyor. Başlangıç düğümüne 0, doğrudan erişilen düğümlere erişim değerleri ve erişilemeyen düğümlere ¥ sonsuz değeri atanıyor. Hedef düğüm olarak da E düğümünü tanımlayalım.

Yukarıdaki örnekte A düğümünden başlayacağımız düşünelim:

Şimdi şekilde kenarları sıralayalım:

AB 2

AC 1

BE -2

BF 5

CF 2

CD -1

DF 5

DE 7

Bellman ford algoritması işte bu kenarları teker teker dolaşması itibariyle dijkstradan ayrılır. Sırayla yukarıdaki kenarları (Edges) dolaşır ve graftaki değerleri günceller.

Yukarıda, rastgele sıra ile dizilen bu kenarları sırasıyla dolaşalım ve bu dolaşma sırasında şu işlemi yapalım.

Örneğin AB kenarı , A ve B düğümleri arasında. Bu düğümlerden düşük değere sahip olan düğüm üzerine kenar değeri eklenip yüksek değere sahip olan düğüm üzerine yazılıyor.

Sırayla gidecek olursak:

AB 2, min(A,B) = 0 à 0+ 2 = 2

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

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

DF 5, min (D,F) = 0 => 0+5 = 5 F’nin değerinden daha büyük o yüzden güncellemiyoruz.

DE 7, min(D,E) = 0 => 0+7 = 7, yine E’nin değerinden büyük olduğu için güncellenmiyor.

Sonuçta graf aşağıdaki şekilde bitmiştir:

Bu graftaki bütün düğümlerde, A düğümünden ne kadar maliyetle gidildiği bulunmuştur. Örnek hedef E düğümü ise, ulaşım maliyeti 4′dür.

Görüldüğü üzere eksi değere sahip düğümler olmasına rağmen herhangi bir problem yaşanmamıştır.

2,296 views