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.

[flashvideo file=http://www.bilgisayarkavramlari.com/wp-content/uploads/bellmanford.flv /]

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.

Yorumlar

  1. Uğur Dönmez

    Algoritmada bir kaç ciddi hata var. Bu şekilde kodlanırsa ciddi problemlere yol açabilir. Ayrıca okuyan kişilerin algoritmayı yanlış öğrenmesine yol açar.

    1. Algoritma Dijkstra nın kısa yol algoritmasından çok farklı. Benzer yönleri sadece kısa yolu bulmaları.

    2. Algoritmanın doğru sonuçlar vermesi için graph da negatif cycle olmaması gereklidir.

    3. Kenarların köşe sayısının bir eksiği kadar olan bir döngüne dolaşılması gereklidir. Sizin yaptığınız gibi tek döngüde olmaz. Tabi kenerları bakıp sıralayınca bazı graph lar tek döngüde çözülür.

    Ayrıntılı bilgi isteyenler algoritmanın doğru şeklini wikipedia dan öğrenebilirler.

    http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

    http://www.ugurdonmez.com

  2. Şadi Evren ŞEKER Article Author

    konuyu tekrar inceleyip hata varsa düzelteceğim. Uyarınız için çok teşekkür ederim.

  3. Gulsum

    Merhaba cd icin eksili sonuc iken be icin farkli bir yol izlenmis sanirim.Orada bir yanlislik mi var.(cd de artili eksili sayilar var ve be icin de eksili artili sayilar var.)

  4. Şadi Evren ŞEKER Article Author

    Kısaca, evet çalışır. Örnek yukarıdaki konuda anlatılan graf. Ancak istisnaları vardır. Bazı durumlarda eksi değer taşıyan kenarlar (edge) sorun olabilir (hangi aşamada karşımıza çıkcağına bağlı). Çünkü undirected demek aslında cycle demektir ve cycle içeren, özellikle de eksi değerli cycle içeren graphlard bu cycle erken aşamalarda karşımıza çıkarsa sorun olacaktır.

    Ayrıca floyd warshall algoritmasına da bakabilirsiniz:
    http://www.bilgisayarkavramlari.com/2009/05/29/floyd-warshall-algoritmasi/

  5. yavuz

    hocam Bellman Ford algorıtması ne tür bir algorıtmadır ac gozlumu yoksa dınamık programlamamı? cvp larsanız sevınırım tss ler..

  6. yavuz

    tss ederm hocam, hocam bfs algoritması ne tip bi algoritmadır? onu sormayı unutmusum cvplarınınz için şimdiden tss edeırm..

  7. Şadi Evren ŞEKER Article Author

    bu “tss etmek” kısmındaki tss neyin kısaltmasıdır?

    sanırım Breadth First Search algoritmasının “ne tip bi algoritma” olduğunu sormak istiyorsunuz.

    Elimizdeki “tipler” nelerdir sayarsanız hangilerine girdiğini söyleyebilirim, yani tam olarak nasıl bir sınıflandırma istiyorsunuz algoritma ile ilgili? Şayet bir önceki sorunuzda olduğu gibi aç gözlü veya dinamik “tiplerinden” birisini kast ediyorsanız ikisine de girmez. BFS için tam olarak adımlar belirlidir ve içeriğe bakmaksızın arama yapar. Ancak aç gözlü yaklaşımı kullanan BFS şekli de vardır ve greedy-bfs olarak geçer. Ancak bu biraz daha sezgisel arama (heuristic search) algoritması ile ilgilidir.

  8. yavuz

    tşk ederim diyodum hocam pardon yanlış yazmışım dikkat etmedim hocam bize sormuşlardı sınavda bfs algoritması ne tip bir algoritmadır? şıklarda ise şunlar vardı
    A) Dinamik programlama
    B) Parçala-yönet
    C) Açgözlü
    D) Kaba-kuvvet
    E) Sezgisel
    doğru şık c midir şimdi

  9. Şadi Evren ŞEKER Article Author

    🙂 iki kere yazınca aynı şekilde ben de yeni bir kavram girdi literatüre sanıp ciddi ciddi aramıştım internette ne demek acaba diye.

    Evet sorunun cevabı C şıkkıdır, açgözlü (Greedy) bir şekilde sıradaki düğümü hiç düşünmeden dolaşır 🙂

    Ancak tabi soruda BFS şeklinde geçtiyse bu durumda bir karmaşa da Brute Force Search ile karışma durumu, sizin sorunuzdaki BFS kısaltmasının Breadth First Search olduğunu kabul ediyorum.

    Ayrıca Breadth First Search üzerinde yapılan değişikliklerle heuristic (sezgisel) veya dinamik programlama olarak da çalışabilir kisi de mümkündür ancak soru bu şekilde ise doğru cevap C şıkkıdır.

    Başarılar

  10. yavuz

    çok tşk ettim hocam cvp ımı aldım sorumdakı BFS (breadth-first-search) di tahmin ettiginiz gibi kolay gelsin..

Bir cevap yazın

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