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.
hocam elinize dilinize sağlık çok iyi olmuş videolu anlatım
hocam elinize saglık canlı canlı daha iyi olmuş
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
konuyu tekrar inceleyip hata varsa düzelteceğim. Uyarınız için çok teşekkür ederim.
İlginiz için ben teşekkür ederim. Kaliteli emek dolu bir siteniz var.
http://www.ugurdonmez.com
Evet döngü sayısı konusunda haklısınız, düğüm sayısı kadar bir dış döngü gerekiyor. Yazıyı yeniden yazıp http://www.bilgisayarkavramlari.com/2010/08/05/bellman-ford-algoritmasi-2/ adresinde yayınladım, bu yazının başına da uyarı ekledim. Tekrar teşekkürler
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.)
Duzeltilmis yazinizi sonradan farkettim.Iyi gunler.
BellmanFord Algoritması Undirected graph’ler icin calısıyor mu?
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/
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..
dinamik programlama kullanır. Yazıda da bahsi geçiyor dijkstra gibi aç gözlü yaklaşımını (greedy approach) kullanmaz.
tss ederm hocam, hocam bfs algoritması ne tip bi algoritmadır? onu sormayı unutmusum cvplarınınz için şimdiden tss edeırm..
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.
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
🙂 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
çok tşk ettim hocam cvp ımı aldım sorumdakı BFS (breadth-first-search) di tahmin ettiginiz gibi kolay gelsin..
merhaba hocam cd yolu -1 cıkarmısda be oluda -2 ondaneden cıkarmamıs..