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. 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 )

Algoritma aşağıdaki şekildedir:

Bütün düğümlere sonsuz mesafesini ata

Her düğüm için

Her kenar için

Düğümün üzerindeki mesafeden daha küçük mesafe bulduysan

Düğüm mesafesini ve düğüme gelinen düğümü güncelle

Yukarıdaki kodda görüldüğü üzere, iç içe iki döngü, kenar ve düğüm sayısı kadar dönmektedir. Ayrıca, bir düğümdeki değerin güncellenmesi sırasında, hangi düğümden gelindiği bilgisi de tutulmaktadır. Bu durum eksi yüklü kenarlar için çözüm oluşturur. Örneğin Dijkstra algoritmasında olan ve negatif değerli kenarlardan kaynaklanan döngüye girilme ihtimali, Bellman-Ford algoritmasında bulunmaz.

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.

Öncelikle eksi değerde düğüm bulunmayan bir örnek üzerinden algoritmayı çalıştıralım.

Öncelikle düğümlere değer ataması yapılıyor. Bütün düğümlere ¥ sonsuz değeri atanıyor.

Ayrıca başlangıç düğümü olarak A, Hedef düğüm olarak da E düğümünü tanımlayalım. Bu düğümleri algoritmanın sonunda kontrol için kullanacağız.

A başlangıç olduğu için 0 değerine sahip.

Önce dolaşacağımız düğümler için bir sıra oluşturalım. Bu örnekte alfabetik olarak düğümleri dolaşacağız ancak bu durum tamamen rast geledir.

Düğüm sıramız: A,B,C,D,E,F olmuş oluyor.

Şimdi de 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.

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:

AB 2

AC 1

BE 2

BF 5

CF 2

CD 1

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 şeklinde, 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.

İkinci Örnek

Yukarıdaki örnekte, düğümlerin ve kenarların rast gele dizildiğinden bahsetmiştik. Acaba bu dizilim rast gele olarak yukarıdakinden farklı olsaydı Bellman-Ford yine başarılı çalışır mıydı?

Düğüm diziliminin sonuca bir etkisi olmamakla beraber, kenar dizilimi sonucu etkiler:

Yukarıdaki dizilimi tersine çevirelim:

DF 5
DE 7
CF 2
CD 1
BF 5
BE 2
AC 1
AB 2

Bu yeni dizilime göre algoritmamızı çalıştırıyoruz:

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.

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

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

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:

CF 2
CD 1
BF 5
BE 2
AC 1
AB 2

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 şeklinde, A,B,C düğümlerinde sonsuz dışında değerler bulunuyor .O halde sadece bu düğümlere komşu olan kenarları almak yeterlidir.

CF 2 için:

CD 1 için

BF 5 için , zaten daha kısa olan 3 değeri bulunmuştur

BE 2 için

AC ve AB kenarları için ise değişiklik olmaz.

Yukarıdaki bu yeni çalışmada dikkat edilirse, bir önceki çalışmadan farklı olarak F düğümü hiç 7 olmadan 3 değerini bulmuştur. Görüldüğü üzere kenar sıralaması, sonucu etkilememekle birlikte çalışma hızını etkileyebilir.

Eksi değerli Şekiller

Gelelim eksi değer olması durumuna.

Yukarıdaki şekilde görüldüğü üzere, BE ve CD kenarları eksi değerlidir. Bu şeklin çalışmasını inceleyelim:

Her şey, normal algoritmada olduğu gibi, başlangıç dışındaki düğümlere sonsuz atayarak başlıyor.

Bu algoritmanın eksi değerlerdeki başarısının anlaşılabilmesi için, şimdiye kadar ihtiyaç duymadığımız ve yazının başında belirtilen, hangi düğümden gelindiği bilgisine ihtiyaç vardır. Yani algoritmamızı çalıştırırken, her düğümdeki değerin güncellenmesi sırasında, hangi düğümden güncellendiği yazılır.

Ardından her düğüm için ve her kenar için işlem yapılıyor. Bu adımları daha önce detaylıca gösterdiğim için aşağıda düğüm bazlı hızlandırılmış olarak anlatıp, sadece eksi değerdeki farkı vurgulayacağım:

Bir sonraki adımda kenar sırasına göre aşağıdaki güncellemeler yapılır:

Bu haliyle, graftaki bütün düğümlere erişilmiştir. Fakat problem bitmez. Yani eksi değerli düğümler, çalışmanın hala devam etmesini gerektirir.

Yukarıdaki son hali, kararlı haldir.

Bu noktada şu soru sorulabilir: Peki neden tekrar eski değerli düğümler işlenerek, D ve E düğümleri güncellemiyor?

Bu soru haklı bir sorudur ancak yazının başında belirtildiği üzere, bellman-ford algoritması, her düğümde, kimden gelindiği bilgisini tutar. Dolayısıyla D düğümünü 0 olarak güncellemeden önce, D düğümüne, C düğümünden gelindiği ve E düğümüne de B düğümünden gelindiği kaydedilmiştir.

Dolayısıyla, eksi değerler tağılan bu döngülerde, tekrar edilip örneğin F düğümüne -4 değeri yazılamaz. Çünkü F düğümü zaten B düğümünden güncellenmiştir.

Yorumlar

  1. bekir

    teşekkur ederim… guzel bir anlatim olmus fakat son şekilde morla -2/F yazılmış B düğümü -2/E olmayacakmi yoksa benmi yanliş anlamişim …

  2. bekir

    peki hocam dijkstrayla bellman ford’un farkini ben pek anlayamadım, tek fark gorduğum nokta eksi değerli duğumlerde dijkstranin calişmamasi bellman ford’un ise calişmasi , aralarinda daha ne gibi farklar var hocam aciklarmisniz ???

  3. Şadi Evren ŞEKER Article Author

    ikisinin arasındaki en önemli fark, bellman ford algritmasının eksi değere sahip kenarlar için kullanılabiliyor olması. Ayrıca dijkstra algoritması daha hızlı çalışır. Bunun dışında problemi çözme metodolijilerin saymazsak bir fark yok.

    başarılar

  4. meryem

    Oncelikle verdiginiz bilgiler icin cok tesekkur ederim,kesinlikle cok yararli oldu benim icin.Belki tamamen bu konuyla ilgili deil ama algoritmalarla ilgili bir soru sormak istiyorum.Zaman ayırır ve sorumu cevaplarsaniz cok memnun olurum.

    maximum flow algoritmalarini kullanarak bir minimum s.t cut bulabilirmiyiz ama kesilen kenar sayisi minimum olmali.bunu nasil gosterebiliriz?

    sorunun orjinal hali;

    Let N = ((V;E); s; t; c) be a network with edge capacities c : E

  5. Şadi Evren ŞEKER Article Author

    meşhur bir sorudur 🙂 kısaca şöyle cevaplayalım, bir graftaki min cut ( st cut yani source target arasındaki en az kenarın kesilmesi) max flow ile aynıdır. Örneğin sitede yayınladığımız Edmonds Karp algoritması veya Ford Fulkerson algoritmasına bakarsanız bu algoritmalarda bulunan en dolu yol min cut için en uygun yollardır. Yine de sorunuzu not alıyorum, siteye eklenecek yazılar listesinde ve sırası gelince bu konuda bir yazı ekleyeceğim.

  6. hakan

    Bellman fordun başlandıç yönü önemli mi en kısa yolu bulmak için acaba? İlle yoların ok ile gösterilip ona göre mi yapılması gerekmektedir?

  7. hakan

    buradaki slaytta 16. bölümde gösterilen örnekte ilk 0. nodedan baslanmıs ama daha sonra hangi sıra ile hesaplanmıs düğümler anlamadım Hocam

  8. Şadi Evren ŞEKER Article Author

    Başlangıç yönü önemli değil. Önemli olan nereden başlarsanız veya ne yönde giderseniz gidin sonuçta düğümlerde güncellediğiniz değerler. Ok ile göstermek ile kast ettiğiniz, yönlü bir şekil olması (directed graph) durumu. Ve evet bellman ford algoritmasında, eski değere sahip döngü (loop) olmaması için yönlü bir şekil olması gerekir. Aksi halde aynı yoldan hem gidip hem gelebileceği için problem olur.

  9. Şadi Evren ŞEKER Article Author

    D ve E düğümlerinden güncellenirler. Yani en son aşamadan bir önceki aşamada son olarak ulaşılan D düğümü (ki değeri 0’dır) ve E düğümü (ki değeri yine 0’dır) bu aşamaya kadar her aşamada olduğu gibi komşularını güncellerler. Güncelleme sonucunda komşuları olan B ve C düğümlerinin kendilerinden güncellenmedğini ve düğüm üzerinde yazan değerden daha düşük değerlerle ulaşılabildiğini görürler. Bu durumda B ve C düğümleri güncellenir.

    Şayet erişilen değerler, düğümlerin üzerinde yazan değerden daha düşük olmasına rağmen, ulaşılan düğüm bilgisi kendileri olsaydı (yani örneğin D düğümüne B düğümündne erişilmiş olsun ve yine B düğümünden D düğümüne erişilen daha ufak bir değer bulunsun) bu durumda dijkstra algoritmasından farklı olarak güncelleme yapılmayacaktı.

    Bu şekilde bütün düğümler değişmeden kararlı hale geçene kadar güncellemeler devam eder ve son güncellenen düğüm komşularını güncelleyerek devam eder.

    Başarılar

    Şadi

  10. javacı

    teşekkürler bir sorum olacak C ve B nin son halini hiç anlamadım ve dijkstra ve bellman ford un java ile yazılmış kaba kodunu yollayabilir misiniz yarına kadar

Bir cevap yazın

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