Edmonds Karp Algoritması

Yazan : Şadi Evren ŞEKER

Bu algoritmanın amacı, literatürde azami akış ( maximum flow ) olarak geçen ve düğümler (nodes) arasında akış kapasiteleri belirli bir şekildeki (graph) bir başlangıçtan bir hedefe en fazla akışın sağlandığı problemleri çözmektir.

Azami akış (maximum flow) problemini örneğin şehirler arasında bağlı boru hattına veya tedarik zincirine benzetebiliriz. Örneğin aşağıdaki şekli ele alalım:

Buradaki düğümler, şehirleri ve düğümler arasındaki kenarlar (edges) ise şehirler arasındaki boru hatlarının kapasitesini belirtsin. Amacımız A düğümünden E düğüme azami miktarda akış sağlayabilmek olsun.

Ford-Fulkerson çözüm için yukarıdaki şekilde öncelikle hedef düğüme giden yolu bulur. Algoritma bu arama işlemi sırasında şayet derin öncelikli arama (depth first search ,DFS) kullanıyorsa ford fulkerson olarak isimlendirilir. Şayet aynı algoritma bu arama işlemi sırasında sığ öncelikli arama (breadth first search, BFS) kullanırsa bu durumda da edmonds karp algoritması olarak isimlendirilir.

Biz yazımızın konusu olan Edmonds Karp algoritmasını anlamak için sığ öncelikli olarak arama işlemini gerçekleştirelim:

BFS (sığ öncelikli arama) sonucunda bulunan yollarımız aşağıda listelenmiş olsun:

• A-D-E
• A-B-E
• A-C-D-E
• A-C-F-B-E
• A-C-F-D-E
• A-B-F-D-E

İlk bulacağımız yol (path) A-D-E olsun bu durumda algoritma bu yol üzerindeki en küçük kapasiteyi bulmaya çalışır:

min(A-D,D-E) = min(5,7) = 5

bu bulunan sayı aslında bu yol üzerinden akabilecek maksimum değerdir. Dolayısıyla bu yoldan 5 kapasitesinde akış yapılmasına karar verilir ve şekil üzerinde bu durum işaretlenir:

Yukarıdaki şekilde buluna kırmızı sayılar, o yoldaki anlık akış miktarlarıdır.

Ardından derin öncelikli arama işlemi devam eder ve örneğin A-B-E yolunu bulur.

min(A-B, B-E) = min(4,2) = 2

Bir sonraki yolumuz olan A-C-D-E yolunu hesaplayalım.

min(A-C,C-D,D-E) = min(1,1,2) = 1

Yukarıda dikkat edilecek bir nokta, D-E aralığının şeklin ilk halinde olan 7 olarak alınması yerine 2 olarak alınmasıdır. Bunun sebebi şeklin bu kenarındaki 5 miktarındaki kapasitenin şu anda kullanılıyor olması ve artık geriye 2 miktarında kapasite kalmasıdır.

Bu adımsan sonra BFS algoritmamız ile bulduğumuz aşağıdaki yolları atlamamız gerekecektir:

• A-C-F-B-E
• A-C-F-D-E

Bunun sebebi bu yollarda bulunan A-C aralığının artık 0 kapasitesinin kalmış olması ve bu yollardan daha fazla akış elde edilememesidir.

Son olarak BFS algoritmamızın bulduğu A-B-F-D-E yolunu hesaplayalım:

min (A-B,B-F,F-D,D-E) = min ( 2,5,5,1) = 1

Yukarıdaki şekilde bütün düğümler arasındaki akışlar gösterilmiştir. Gerçekten de graftaki E düğümüne (hedef düğüme) gidebilen yollar maksimum kapasite ile doldurulmuştur.