Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinin önemli konularından olan algoritma analizi sırasında sıkça bahsi geçen bir algoritmadır. Algoritmanın ana amacı belirli bir graf üzerinde bir başlangıçtan(source) bir bitiş düğümüne (sink, end, target)  en kısa yoldan (shortest path) ulaşmaktır.

Bu özelliğinden dolayı, maksimum akış (maximum flow) problemleri olarak bilinen, ve örneğin bir dağıtım şebekesinde bir kaynaktan bir hedefe gönderilebilecek azami miktarı sevk eden problemlerin çözümünde kullanılabilen bu algoritma, algoritmayı bulan iki kişinin ismi ile anılmaktadır.

İçerik
1. Algoritma
2. Örnek
3. Algoritmanın kullanım alanları

Bu algoritmanın ana amcı dinamik programlama (dynamic programming) konusunu daha iyi anlayabilmektir.

Algoritma

Algoritma basitçe bir grafta gidilebilecek düğümlerin komşuluk listesini (adjecency list) çıkararak bu düğümlere olan mesafeyi tutan bir masfuf (matris) üzerinden çalışır.

Algoritmanın her adımında matris üzerinde çeşitli işlemler yapılarak en kısa yol bulunmaya çalışılır.

Algoritma matris üzerinde çalışan ve düğümler arası mesafeleri her adımda güncelleyen bir algoritma olduğu için itartif (iterative, döngü ile) yazılabilir. Aşağıda müsvette kodlar (pseude codes) verilmiştir.

 1 int yol[][];
 2 /* Sonucun içinde bulunacağı ve anlık olarak bir düğümden
 3    diğerine ne kadar maliyet ile bulunduğunu tutan matris.
 4    İlk olarak komşuluk listesini tutar ve doğrudan
 5 gidilemeyen düğümlere olan mesafe sonsuz olarak tutulur.*/
 6
 7 procedure FloydWarshall ()
 8    for k: = 1 to n
 9       for each (i,j) in{1,..,n}2
10          yol[i][j] = min ( yol[i][j], yol[i][k]+yol[k][j] );

Yukarıdaki algoritmada görüldüğü üzere n adet düğümlü bir graf için iki boyutlu bir dizi oluşturulur. Bu dizinin içerisindeki değerlere ilk olarak komşuluk listesindeki değerler atanır ve doğrudan ulaşılamayan düğümler için sonsuz değeri doldurulur.

Ardından Matrisi dolaşan bir döngü ile (i ve j) yollar güncellenir. Bu matrisin taranması işlemi düğüm sayısı (n) kadar tekrar eder (yukarıdaki k döngü değişkeni tekrara yaramaktadır). Bu tekrar aslında üzerinden atlanma ihtimali olan düğümü belirtmektedir. Yani örneğin k = 3 için 3. düğüm marifetiyle ulaşılan düğümler belirlenir. (örneğin 1. düğümden 4. düğüme doğrudan erişim yoksa ama 1. düğümden 3. düğüme ve 3. düğümden de 4. düğüme erişim varsa )

Yukarıdaki algoritma daha basit bir şekilde yazılabilir:

for i = 1 to N
   for j = 1 to N
      if(i'den j'ye bir yol varsa)
         yol[0][i][j] = i ile j arasındaki mesafe
      else
         yol[0][i][j] = sonsuz

for k = 1 to N
   for i = 1 to N
      for j = 1 to N
         yol[k][i][j] = min(yol[k-1][i][j], yol[k-1][i][k]
+ yol[k-1][k][j])

Algoritmanın çalışmasına örnek

Algoritmanın çalışmasını daha iyi anlayabilmek için aşağıdaki örnek üzerinden adım adım algoritmayı kullanarak en kısa yolu bulalım:
floyd_warshall

Yukarıdaki şekil incelendiğinde A’dan E’ye giden birden çok yol bulunabilir:

Yol 1:    A -> B -> E             20
Yol 2:    A -> D -> E             25
Yol 3:    A -> B -> D -> E        35
Yol 4:    A -> D -> B -> E        20

Yukarıdaki yollar çıkarıldıktan sonra en kısasının 20 uzunluğunda olduğu bulunabilir. Şimdi bu yollardan en kısasını Floyd-Warshall algoritmasının nasıl bulduğunu adım adım inceleyelim:
1. Adımda komşuluk listesine göre matris inşa edilir.

Yukarıdaki şekilde doğrudan ilişkisi bulunan düğümler ve ağırlıkları aşağıda verilmiştir:

    A   B   C   D   E
A   0  10   ∞   5   ∞
B  10   0   5   5  10
C   ∞   5   0   ∞   ∞
D   5   5   ∞   0  20
E   ∞  10   ∞  20   0

Yukarıdaki grafta doğrudan ilişkisi bulunmayan düğümlerin değerleri ∞ olarak gösterilmektedir. Diğer değerler doğrudan ağırlıkları göstermektedir.

Şimdi algoritmanın 2. adımına geçerek yolların tutulduğu bu matrisi adım adım güncelleyelim:

    A   B   C   D   E
A   0  10   ∞   5   ∞
B  10   0   5   5  10
C   ∞   5   0   ∞   ∞
D   5   5   ∞   0  20
E   ∞  10   ∞  20   0

B üzerinden atlanarak ulaşılan düğümleri güncelleyelim

    A   B   C   D   E
A   0  10  15   5  20
B  10   0   5   5  10
C  15   5   0  10  15
D   5   5  10   0  15
E  20  10  15   15  0

C üzerinden atlanan düğümler:

    A   B   C   D   E
A   0  10  15   5  20
B  10   0   5   5  10
C  15   5   0  10  15
D   5   5  10   0  15
E  20  10  15  15   0

D üzerinden atlanan düğümler:

    A   B   C   D   E
A   0  10  15   5  20
B  10   0   5   5  10
C  15   5   0  10  15
D   5   5  10   0  15
E  20  10  15  15   0

E üzerinden atlanan düğümler:

    A   B   C   D   E
A   0  10  15   5  20
B  10   0   5   5  10
C  15   5   0  10  15
D   5   5  10   0  15
E  20  10  15  15   0

Yukarıda son elde edilen bu matriste görüldüğü üzere herhangi bir düğümden diğer bütün düğümlere giden en kısa yollar çıkarılmıştır. Örneğin A düğümünden E’ye 20 uzunluğunda veya C düğümünden D’ye 10 uzunluğunda yolla gidilebilir.

Yukarıdaki matrislerde diyagona göre simetri bulunmasının sebebi grafın yönsüz graf (undirected graph) olmasıdır. Şayet graf yönlü graf (directed graph) olsaydı bu simetri bozulurdu (tabi yönlerin ağırlıklarının aynı olmaması durumunda).

Algoritmanın kullanım alanları

Floyd-Warshall algoritması aşağıdaki amaçlar için kullanılabilir:

  • Yönlü graflarda en kısa yolun bulunması için. (Yukarıda bu durumu gösteren bir örnek bulunmakta)
  • Bir düğümden seyahat edilebilecek diğer düğümlerin bulunmasında (transitive closure). Örneğin matrisin ilk halinde gidilemeyen düğümler sonsuz değerine sahiptir. Şayet matris işlendikten sonra hala sonsuz değerine sahip matris elemanı bulunursa bunun anlamı o satır ve sütündakı düğümler arasında gidişin aktarmalı da olsa mümkün olmadığıdır.
  • Düzenli ifadelerde (regular expressions) herhangi bir tekrarlı olayın tespiti için kullanılabilir. Kleen yıldızı (kleen’s algorithm) şeklinde tekrar eden ifadelerin bulunmasına yarar. Şayet çıkan matriste bir düğümden diğer düğüme giden yol sonsuz değilse ve diyagona göre simetriği olan yol da sonsuz değilse bir kleen yıldızı üretilebilir.
  • Ağ programlamasında özellikle yönlendirici algoritmalarında (routing algorithms) en kısa yolun tayin edilmesinde kullanılabilir.
  • Yönsüz bir grafın (undirected graph), iki parçalı graf (bipartite graph) olup olmadığının bulunmasında kullanılabilir. Basitçe graftaki mesafelerin tamamını 1 uzunluğunda kabul edersek (veya mesafe olarak atlanan düğüm sayısını (hop count) kabul edersek) bu durumda bir düğümden gidilebilen bütün komşu düğümlerin mesafesi ya tek ya da çift olmalıdır. Bir düğümün hem tek hem de çift komşusu varsa bipartite değildir denilebilir.

Yorumlar

  1. sss

    A B C D E
    A 0 10 ∞ 5 0
    B 10 0 5 5 10
    C ∞ 5 0 ∞ 0
    D 5 5 ∞ 0 20
    E ∞ 10 ∞ 20 0

    bu matris de e den a ya ve e den c ye sonsuz olması gerekmiyor mu?

  2. Şadi Evren ŞEKER Article Author

    evet haklısınız, ilk matriste 0 yazılarak hata yapılmış (sonrakilerinde düzeltilmiş ama ilki hatalı) uyarınız için teşekkür ederim, yazının içerisinde gerekli düzeltmeyi yapıyorum.

  3. emre

    E’den D’ye E üzerinden atlanan düğümler matrisinde mesafew 20. Fakat siz 5 alarak direk mesafeyi yazmışsınız. Bunu yazarken algoritmanın büyüklük kıyaslaması yaptığını hesaplayarakmi oluşturdunuz?

  4. emre

    Az önce yanlış yazdım, düzeltiyorum. B den D ye E üzerinden giden matris te mesafe 30. fakat matris te 5 yazıyor. Algoritma büyüklük kıyaslaması yaptıktan sonra bu değeri yazıyor diye mi 5 yazdık? İyi günler.

  5. Şadi Evren ŞEKER Article Author

    30 tam olarak nerede? Yukarıdaki matrislere tekrar tekrar bakıyorum ama b-d arası hep 5 olarak geçmiş ki şekilde de durum bu şekilde.

    B’den D’ye E üzerinden gitmek diye bir durum söz konusu değil. Sorumuzda A’dan başlanıp E’de bitmesi istenmiş. Yukarıdaki yazıdaki alternatif yollar bunların değerini tutuyor.

    Şayet kast ettiğiniz örneğin son matristeki

        A   B   C   D   E
    A   0  10  15   5  20
    B  10   0   5   5  10
    C  15   5   0  10  15
    D   5   5  10   0  15
    E  20  10  15  15   0
    

    E üzerinden atlanan değerler yazısı ise.

    Burada sanırım bir yanlış anlama var. E üzerinden atlandıktan sonraki değerler güncellenirken matristeki değerlerden daha düşük bir değer varsa yazılır. Sizin belirttiğiniz gibi belki b-e-d dolaşması 30 değerinde ama daha kısa olan ve doğrudan b-d bağlantısı (5) olduğu için bu değer değiştirilmemiş.

    Unutmayın ki en kısa yolu arıyoruz.

    Başarılar

  6. anıl

    Sadece 10 dakikada okuyup anlayabileceğim bu sayfayı geçen dönem okumadığım için, şu anda algoritma analizi dersini tekrar alıyorum. Vizede çıktı yapamadım, bütünlemede bir daha çıktı ve yine yapamadım. bilgisayarkavramlari.com a ciddi bir teşekkür borçluyum. Üzerimde emeği hayli çok olan bir site

  7. ercan

    Teşekkürler hocam çok güzel anlatmışsınız, bi algoritmaya ihtiyaç duyduğumda google’dan önce ilk bilgisayarkavramlari.com’ a bakıyorum

  8. adem

    hocam b den atlamalı duğumde a dan d ye 5 olarak yazmışsınız ama 10 olması gerekmiyor mu yoksa ben mi yanlış anladım?:( 5 ise neden o şekilde yaptık.teşşekkr ederim şimdiden

Bir cevap yazın

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