بیشینه‌ی جریان (ادموندز–کارپ)

تا وقتی در شبکه‌ی باقی‌مانده مسیری از مبدأ به آخرین گره هست، کوتاه‌ترینش را با BFS پیدا می‌کند و جریان را از آن عبور می‌دهد.

هر یال یک ظرفیت دارد. می‌خواهیم بیشترین جریان ممکن را از مبدأ (اینجا گره‌ی انتخاب‌شده) به مقصد (آخرین گره) بفرستیم، بی‌آنکه از ظرفیت هیچ یالی بیشتر شود و هر چه به گره‌ای وارد می‌شود از آن خارج شود.

ادامه‌ی توضیح ↓

زمان: O(V · E²)
حافظه: O(V + E)
CLRS، بخش ۲۴.۲
گریمالدی، فصل ۱۳

ورودی:

V=6 · E=9 · src=Sخروجی PDF

شبکه‌ی شش‌گره‌ای مشهور با مبدأ S و مقصد T؛ بیشینه‌ی جریان ۲۳ است.

from collections import deque
INF = float("inf")
def edmonds_karp(graph, s):
t = list(graph)[-1] # the last node is the sink
cap = {u: {} for u in graph}
for u in graph:
for v, w in graph[u]:
cap[u][v] = cap[u].get(v, 0) + w
cap[v].setdefault(u, 0)
total = 0
while True:
parent = {v: None for v in graph}
seen = {s}
queue = deque([s])
while queue and t not in seen:
u = queue.popleft()
for v in cap[u]:
if cap[u][v] == 0 or v in seen:
continue
seen.add(v)
parent[v] = u
queue.append(v)
if t not in seen:
return total
bottleneck = INF
v = t
while v != s:
bottleneck = min(bottleneck, cap[parent[v]][v])
v = parent[v]
v = t
while v != s:
u = parent[v]
cap[u][v] = cap[u][v] - bottleneck
cap[v][u] = cap[v][u] + bottleneck
v = u
total = total + bottleneck

ناوردا: cap[u][v] همیشه ظرفیت باقی‌مانده است: ظرفیت یال منهای جریانش، به‌اضافه‌ی جریانی که می‌شود از یال برعکس پس گرفت.

شروع اجرا

گره‌ی جاری (u)
درخت پیمایش (از parent)
یالِ در حال بررسی

صف `queue`

خالی

متغیرهای محلی

s'S'

نارنجی = در همین گام عوض شد

graph dict

'S': [('A', 16), ('B', 13)]
'A': [('C', 12)]
'B': [('A', 4), ('D', 14)]
'C': [('B', 9), ('T', 20)]
'D': [('C', 7), ('T', 4)]
'T': []

Call stack

edmonds_karp()خط 6

گام ۱ از ۴۱۳

رشد تعداد عملیات با اندازه‌ی ورودی

میانگین ۵ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.

take
push
ورودی فعلی (n=6)

نمایش به شکل جدول

n	take	push
4	7.8	5.2
8	20.4	8.8
12	28.2	11.6

توضیح

ایده

روش فورد–فالکرسون

در شبکه‌ی باقی‌مانده (ظرفیت‌هایی که هنوز آزادند) یک مسیر از مبدأ به مقصد پیدا کن: مسیر افزایشی.
کمترین ظرفیت روی مسیر (گلوگاه) را بفرست.
برای هر یال u → v که جریان گرفت، به یال برعکس v → u همان‌قدر ظرفیت بده تا بعداً بشود این جریان را پس گرفت.

تا وقتی مسیر افزایشی هست ادامه بده. قضیه‌ی جریان بیشینه – برش کمینه می‌گوید جوابِ پایانی بهینه است.

چرا BFS؟

ادموندز و کارپ نشان دادند اگر همیشه کوتاه‌ترین مسیر (با BFS) را برداریم، تعداد دورها حداکثر O(V·E) است: جمعاً O(V·E²)، مستقل از اندازه‌ی ظرفیت‌ها.

در trace به چه چیزی نگاه کنی

یال‌های رنگی درخت BFS فعلی‌اند و مسیر افزایشی روی آن است.
دیکشنری cap در پنل حافظه ظرفیت‌های باقی‌مانده است؛ ورودی «پس گرفتن جریان» استفاده از یال برعکس را نشان می‌دهد.