Floyd-Warshall Algoritması

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:

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.

∞