الگوریتم فورد–فالکرسون کیست؟ توضیح بده.
الگوریتم فورد-فالکرسون، مسئله بیشینه جریان را در شبکه‌های جریان حل می‌کند. این الگوریتم در سال ۱۹۵۶ منتشر شد. نام این الگوریتم به جای الگوریتم ادموندز کارپ هم به کار می‌رود.ایده اصلی این الگوریتم بسیار ساده‌است: تا جایی که راهی از منبع (گره شروع) به چاهک (گره پایانی)، با یال وزن دار وجود دارد، می‌توان جریان را از یکی از این مسیرها عبور داد. سپس مسیر دیگری پیدا می‌شود و همین طور الگوریتم ادامه پیدا می‌کند.الگوریتم.در گراف داده شده G با ظرفیت c و جریان f(u،v)=۰ برای یالی از formula_1 به formula_2 می‌خواهیم بیشترین جریان از منبع s به چاهک t را پیدا کنیم. بعد از هر مرحله در الگوریتم موارد زیر پیش می‌آید:در صورت برقراری این سه شرط، شبکه یک جریان قانونی بعد از هر مرحله خواهد داشت. ما شبکه پسماند را اینگونه تعریف می‌کنیم،شبکه پسماند formula_11 شبکه ایست که ظرفیتش اینگونه بدست می‌آید: formula_12توجه کنید که ممکن است جریانی از formula_2 به formula_1 وجود داشته باشد، که در شبکه‌های پسماند قانونی است ولی در شبکه اصلی غیر مجاز است: اگر f(u،v)&gt;۰ و c(v،u)=۰ آنگاه cf(v،u)&gt;۰. {Cfp=min {cf(u،v)|(u.v) ϵP را پیدا کن.برای هر یال عضو p داریمf(u،v)⟵ f(u,v) + Cfpf(v،u)⟵ f(v,u) - Cfp برای پیدا کردن مسیر در مرحله ۲ می‌توان از الگوریتم‌های بی اف اس یا DFS استفاده کرد. وقتی که مسیر دیگری در مرحله ۲ پیدا نشود، s به t در شبکه پشماند نمی‌رسد. اگر S مجموعه‌ای از گره‌های قابل دست رسی برای s در شبکهٔ پشماند باشد، آنگاه مجموع ظرفیت در شبکه اصلی یال‌ها از S به V در یک طرف برابر است با مجوع جریان‌هایی از s به t پیدا کرده‌ایم. این نشان می‌دهد که بیشترین جریان پیدا شده‌است.تحلیل الگوریتم.زمان اجرای این الگوریتم به این بستگی دارد که مسیر P چگونه انتخاب شود. اگر بد انتخاب شده باشد ممکن است الگوریتم خانمه نیابد: مقدار جریان با تکمبل کردن‌های پیاپی افزایش خواهد یافت، لزوماً به مقدار ماکزیمم جریان همگرایی پیدا نمی‌کند. هر چند اگر مسیر تکمیلی با استفاده از الگوریتم جستجوی اول سطح انتخاب شود الگوریتم با مرتبه زمانی چند جمله‌ای اجرا می‌گردد.در حالت کلی زمان اجرا از (O(E*f است، که E یال‌های گراف و f بیشترین جریان است. چون پیدا کردن هر مسیر از (O(E طول می‌کشد، همچنین از (O(۱طول می‌کشد تا جریانی اضافه شود.پیاده سازی.class FlowNetwork(object): def __init__(self): 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&gt; 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))مثال عملی.»&gt; g = FlowNetwork()»&gt; [g.add_vertex(v) for v in "sopqrt"][None, None, None, None, None, None]»&gt; g.add_edge('s','o',3)»&gt; g.add_edge('s','p',3)»&gt; g.add_edge('o','p',2)»&gt; g.add_edge('o','q',3)»&gt; g.add_edge('p','r',2)»&gt; g.add_edge('r','t',3)»&gt; g.add_edge('q','r',4)»&gt; g.add_edge('q','t',2)»&gt; print (g.max_flow('s','t'))5