Ford-Fulkerson
- Algoritmalar kursu
- Uzman seviye
- Ders 26/41
- 4 dk
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.
Başlangıç kodu
def ford_fulkerson(capacity, source, sink):
# Maksimum akışı döndürÖrnek çözüm
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'))Beklenen çıktı
5
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 darboğaz akışı
bottleneck = min(flow, capacity[u][____])bottleneck = min(flow, capacity[u][v])Açıklama: capacity[u][v] ile darboğaz hesaplanır.
2 Ford-Fulkerson ne zaman durur?
while augmenting_path_exists():
push_flow()- Kaynak dolunca
- Hedef dolunca
- Artık yol kalmayınca Doğru cevap
- Tüm kenarlar dolunca
Açıklama: Artık yol kalmadığında maksimum akışa ulaşılmıştır.
3 Ford-Fulkerson kavramları
| Kavram | Anlamı |
|---|---|
artık yol |
Akış artırma |
darboğaz |
Minimum kalan kapasite |
geri kenar |
Akış geri çekme |
maksimum akış |
Artık yol yok |