الگوریتم‌های حل مسئله بیشینه جریان
در اینجا دو الگوریتم معروف در این زمینه را معرفی می نمایم
ا
لگوریتم فورد-فالکرسون
مسئله بیشینه جریان را در شبکه‌های جریان حل می‌کند. این الگوریتم در سال ۱۹۵۶ منتشر شد. نام این الگوریتم به جای الگوریتم ادموندز-کارپ هم به کار می‌رود. ایده اصلی این الگوریتم بسیار ساده ‌است: تا جایی که راهی از منبع (گره شروع) به چاهک (گره پایانی)، با یال وزن دار وجود دارد، می‌توان جریان را از یکی از این مسیرها عبور داد. سپس مسیر دیگری پیدا می‌شود و همین طور الگوریتم ادامه پیدا می‌کند.
ورودی: گراف G با ظرفیت c، یک منبع s و یک چاه t.
خروجی: بیشترین جریان f از s به t.
۱»برای تمام یال‌ها۰f(u,v→

۲»تا زمانی که مسیر P از s به t در G وجود دارد،
{Cf(p)=min {cf(u,v)|(u.v) ϵP را پیدا کن.
اگرS مجموعه‌ای از گره‌های قابل دست رسی برای s در شبکهٔ پشماند باشد، آنگاه مجموع ظرفیت در شبکه اصلی یال‌ها از S به V در یک طرف برابر است با مجموع جریان‌هایی از s به t پیدا کرده‌ایم. این نشان می‌دهد که بیشترین جریان پیدا شده ‌است.
زمان اجرای این الگوریتم به این بستگی دارد که مسیر P چگونه انتخاب شود. اگر بد انتخاب شده باشد ممکن است الگوریتم خانمه نیابد مقدار جریان با تکمیل کردن‌های پیاپی افزایش خواهد یافت، لزوماً به مقدار ماکزیمم جریان همگرایی پیدا نمی‌کند. هر چند اگر مسیر تکمیلی با بهره گرفتن از الگوریتم جستجوی اول سطح انتخاب شود الگوریتم با مرتبه زمانی چند جمله‌ای اجرا می‌گردد. در حالت کلی زمان اجرا از (O(E*f است، که E یال‌های گراف و f بیشترین جریان است. چون پیدا کردن هر مسیر از O(E) طول می‌کشد، همچنین از O(1) طول می‌کشد تا جریانی اضافه شود.
class FlowNetwork(object):
def __init__(self):
self.adj, self.flow, = {},{}
def add_vertex(self, vertex):
self.adj[vertex] = []
def get_edges(self, v):
return self.adj[v]
def add_edge(self, u,v,w=0):
self.adj[u].append((v,w))
self.adj[v].append((u,0))
self.flow[(u,v)] = self.flow[(v,u)] = 0
def find_path(self, source, sink, path):
if source == sink:
return path
for vertex, capacity in self.get_edges(source):
residual = capacity - self.flow[(source,vertex)]
edge = (source,vertex,residual)
if residual> 0 and not edge in path:
result = self.find_path(vertex, sink, path + [edge])
if result != None:
return result
def max_flow(self, source, sink):
path = self.find_path(source, sink, [])
while path != None:
flow = min(r for u,v,r in path)
for u,v,_ in path:
self.flow[(u,v)] += flow
self.flow[(v,u)] -= flow
path = self.find_path(source, sink, [])
return sum(self.flow[(source, vertex)] for vertex,
capacity in self.get_edges
(source))
شکل ‏۲‑۱ الگوریتم فورد-فالکرسون.
الگوریتم های ارسال پیش جریان
دسته دیگری از الگوریتم های جریان بیشینه، الگوریتم های ارسال پیش جریان هستند. این الگوریتم ها در هر مرحله میانی، یک پیش جریان را حفظ می‌کنند. نمونه‌ای ‌از این الگوریتم ها، الگوریتم [۱۲] است. در این الگوریتم به جای ارسال جریان در امتداد مسیرها، جریان روی کمان های خاصی ارسال می‌شود. این الگوریتم در طی زمان اجرای خود یک جریان شدنی را حفظ نمی‌کند عمل افزایشی را روی کمانها انجام می‌دهد تا جریان را به شدنی بودن نزدیک کند.
به طور خلاصه می‌توان گفت در الگوریتم های ارسال پیش جریان در هر مرحله، گراف داراری رئوسی با اضافه جریان است. این الگوریتم ها به صورت تکراری جریان در رئوس دارای اضافه جریان، توسط ارسال پیش روی جریان از این رئوس به رأس مقصد و یا ارسال پس رو به رأس مبدأ، کاهش می‌دهند، در حالی که الگوریتم های مسیر افزایشی، محدودیت های توازن جریان را در همه رئوس به غیر از رئوس مبدا و مقصد حفظ می‌کنند. این الگوریتم ها به صورت تکراری جربان را در امتداد مسیرهایی از رأس مبدأ به رأس مقصد افزایش می‌دهند.
روش تحقیق