Algoritmalar
Ford-Fulkerson
Ford-Fulkerson yöntemiyle maksimum akış bulmayı öğrenirsin.
Ford-Fulkerson
Ford-Fulkerson, bir akış ağında maksimum akışı bulan yöntemdir. Temel fikir, artık yollar bulup akışı artırmaktır.
Bir artık yol, kaynaktan hedefe, üzerinde ek akış geçirilebilecek bir yoldur. Her artık yol bulunduğunda, yolun darboğaz değerince akış artırılır.
Artık yol kalmadığında, ulaşılan maksimum akış değeridir. Yöntem, yol seçim yöntemine göre değişen karmaşıklığa sahiptir.
Artık graf
Artık graf, her kenar için kalan kapasiteyi ve geriye dönük akışı gösterir. Bir (u,v) kenarında c_f(u,v) = c(u,v) - f(u,v)'dir.
Akış azaltıldığında geri kenar (v,u) oluşur; bu, akışı geri çekmeye izin verir. Artık yollar bu grafta aranır.
Bu yapı, Ford-Fulkerson'ın akışı hem artırma hem geri çekme yeteneğini sağlar.
Uygulama ford_fulkerson fonksiyonu
ford_fulkerson(capacity, source, sink) yaz. capacity kenar listesi (u, v, c); maksimum akışı döndür. print(ford_fulkerson([('s','a',3), ('s','b',2), ('a','t',2), ('b','t',3), ('a','b',1)], 's', 't')) ile 5 yazdır.
Örnek çözümü göster
def ford_fulkerson(capacity, source, sink):
# Maksimum akışı döndür
from collections import defaultdict
graph = defaultdict(dict)
for u, v, c in capacity:
graph[u][v] = graph[u].get(v, 0) + c
graph[v][u] = graph[v].get(u, 0)
max_flow = 0
def dfs(s, t, flow, visited):
if s == t:
return flow
visited.add(s)
for v in graph[s]:
if v not in visited and graph[s][v] > 0:
pushed = dfs(v, t, min(flow, graph[s][v]), visited)
if pushed > 0:
graph[s][v] -= pushed
graph[v][s] = graph[v].get(s, 0) + pushed
return pushed
return 0
while True:
visited = set()
f = dfs(source, sink, float('inf'), visited)
if f == 0:
break
max_flow += f
return max_flow
print(ford_fulkerson([('s','a',3), ('s','b',2), ('a','t',2), ('b','t',3), ('a','b',1)], 's', 't'))
Kendini test et
-
darboğaz akışı
bottleneck = min(flow, capacity[u][____])
Cevabı göster
bottleneck = min(flow, capacity[u][v])
-
Ford-Fulkerson ne zaman durur?
while augmenting_path_exists():
push_flow()
- Kaynak dolunca
- Hedef dolunca
- Artık yol kalmayınca
- Tüm kenarlar dolunca
Cevabı göster
Artık yol kalmayınca — Artık yol kalmadığında maksimum akışa ulaşılmıştır.
-
Ford-Fulkerson kavramları
- artık yol
- Akış artırma
- darboğaz
- Minimum kalan kapasite
- geri kenar
- Akış geri çekme
- maksimum akış
- Artık yol yok
Sıradaki ders: Edmonds-Karp
