<\/p>\n
Updated August 2026 \u2014 tutorial restored for this URL.<\/em><\/p>\n We are going to consider the Ford-Fulkerson<\/strong> method, which finds a maximum flow<\/strong> in a flow network. If you are new to the topic, read Introduction to Network Flow<\/a> and Cuts in a Network<\/a> first. A worked companion post is also here: The Ford-Fulkerson Algorithm<\/a>.<\/p>\n We will cover:<\/p>\n 1. What is a flow network?<\/strong><\/p>\n A flow network is a directed graph where each edge has a non-negative capacity<\/strong>. We designate:<\/p>\n A flow<\/strong> assigns a value to each edge such that:<\/p>\n The value<\/strong> of the flow is the net amount leaving the source (equivalently, entering the sink).<\/p>\n 2. What Ford-Fulkerson does<\/strong><\/p>\n Ford-Fulkerson repeatedly finds a path from 3. Residual graph and augmenting paths<\/strong><\/p>\n The residual graph<\/strong> tracks leftover capacity:<\/p>\n An augmenting path<\/strong> is any Bottleneck of a path = minimum residual capacity on that path. That is how much flow you can add in one augmentation.<\/p>\n 4. Algorithm steps<\/strong><\/p>\n Pseudocode:<\/p>\n 5. Small example (intuition)<\/strong><\/p>\n Suppose Work the same idea on larger graphs by always searching the residual graph (DFS or BFS).<\/p>\n Python-style sketch<\/strong> (educational \u2014 not production-optimized):<\/p>\n Initialize 6. Complexity and variants<\/strong><\/p>\n 7. Where to go next<\/strong><\/p>\n Updated August 2026 \u2014 tutorial restored for this URL. We are going to consider the Ford-Fulkerson method, which finds a maximum flow in a flow … <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"pagelayer_contact_templates":[],"_pagelayer_content":"","footnotes":""},"categories":[35],"tags":[],"class_list":["post-2296","post","type-post","status-publish","format-standard","hentry","category-algorithms"],"acf":[],"_links":{"self":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/2296","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/comments?post=2296"}],"version-history":[{"count":2,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/2296\/revisions"}],"predecessor-version":[{"id":2437,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/2296\/revisions\/2437"}],"wp:attachment":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/media?parent=2296"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/categories?post=2296"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/tags?post=2296"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\n
\n
s<\/code> \u2014 where flow starts<\/li>\nt<\/code> \u2014 where flow ends<\/li>\n<\/ul>\n\n
s<\/code> and t<\/code>, inflow = outflow (conservation)<\/li>\n<\/ul>\ns<\/code> to t<\/code> that can still carry more flow (an augmenting path<\/strong>), pushes as much as possible along that path, and updates residual capacities \u2014 until no augmenting path remains. At that point the flow is maximum (max-flow min-cut theorem).<\/p>\n\n
s<\/code>\u2192t<\/code> path in the residual graph with positive residual capacity on every edge.<\/p>\n\n
p<\/code> from s<\/code> to t<\/code>:\n\n
b =<\/code> bottleneck(p)<\/li>\np<\/code>: flow += b<\/code><\/li>\np<\/code>: flow \u2212= b<\/code><\/li>\nFord-Fulkerson(G, s, t):\n flow \u2190 0 for all edges\n while exists path p from s to t in residual(G):\n b \u2190 min residual capacity on p\n augment flow along p by b\n return value(flow)\n<\/code><\/pre>\ns \u2192 a<\/code> has capacity 10, a \u2192 t<\/code> has capacity 6, and s \u2192 t<\/code> has capacity 3.<\/p>\n\n
s-a-t<\/code> can push 6 (bottleneck at a-t<\/code>). Flow value = 6.<\/li>\ns-a<\/code> has 4 left; a-t<\/code> is saturated.<\/li>\ns-t<\/code> can push 3. Flow value = 9.<\/li>\nfrom collections import defaultdict, deque\n\ndef edmonds_karp(capacity, s, t):\n # capacity[u][v] = residual capacity\n def bfs():\n parent = {s: None}\n q = deque([s])\n while q:\n u = q.popleft()\n for v, cap in capacity[u].items():\n if v not in parent and cap > 0:\n parent[v] = u\n if v == t:\n return parent\n q.append(v)\n return None\n\n flow_value = 0\n while True:\n parent = bfs()\n if not parent:\n break\n # bottleneck\n v = t\n b = float(\"inf\")\n while v != s:\n u = parent[v]\n b = min(b, capacity[u][v])\n v = u\n # augment\n v = t\n while v != s:\n u = parent[v]\n capacity[u][v] -= b\n capacity[v][u] += b\n v = u\n flow_value += b\n return flow_value\n<\/code><\/pre>\ncapacity<\/code> as a nested dict of edge capacities, and add reverse edges with 0 capacity before running.<\/p>\n\n
\n