{"id":1959,"date":"2018-12-31T12:00:00","date_gmt":"2018-12-31T11:00:00","guid":{"rendered":"https:\/\/kindsonthegenius.com\/blog\/ford-fulkerson-algorithm-for-max-flow-problem\/"},"modified":"2026-07-05T03:24:57","modified_gmt":"2026-07-05T01:24:57","slug":"ford-fulkerson-algorithm-for-max-flow-problem","status":"publish","type":"post","link":"https:\/\/kindsonthegenius.com\/blog\/ford-fulkerson-algorithm-for-max-flow-problem\/","title":{"rendered":"Ford-Fulkerson Algorithm for Max Flow Problem"},"content":{"rendered":"

We cover the following<\/p>\n

    \n
  1. Introduction to Ford-Fulkerson Algorithm<\/a><\/li>\n
  2. Introduction to Residual Graphs<\/a><\/li>\n
  3. About Residual Graphs<\/a><\/li>\n
  4. Augmenting Paths in Residual Graph Using Bottleneck<\/a><\/li>\n<\/ol>\n

    \"\"<\/p>\n

    1. Introduction to Ford-Fulkerson Algorithm<\/strong><\/p>\n

    The Ford-Fulkerson algorithm is the algorithm used to find the max flow through a network. So given a network with the capacities of the edges,\u00a0 how do we assign flow to the edges until\u00a0 we get the max flow?<\/p>\n

    This is how it works:<\/p>\n

    Start by assigning\u00a0 a flow of 0 (f(e) = 0) to all the edges. Then check that the capacity constraint and the conservation constraint have not been violated.<\/p>\n

    Then choose particular path from s to t and increase the flow along that path. This is illustrated in Figure 1 a -f.<\/p>\n

    \"\"
    Figure 1: How Ford-Fulkerson Algorithm Works<\/figcaption><\/figure>\n
      \n
    • From Figure 1.a, we can see the initial network with capacities for each of the edges.<\/li>\n
    • In 1b, we start by assigning a flow of 0 (f(e) = 0 to all edges<\/li>\n
    • In 1c, we choose a path (s-u-v-t) so that that we can increase flow in this path.<\/li>\n
    • In 1d, we increase the flow on all the edges on this path by 20\u00a0 while leaving f(e) = 0 on other two edges (s,v) and (u,t)<\/li>\n
    • At this point, we can check if we have achieved the maximum flow through the network. The answer is no, because we have a flow of 20 but the capacity of the network is 30. So we can improve the flow.<\/li>\n
    • So in 1e, we subtract a flow of 10 from edge (u, v). This is a equivalent to adding a backward flow of 10 from on edge (v,u).<\/li>\n
    • Finally in 1f, we add a flow of 10 to edges (s, v) and (u, t).<\/li>\n<\/ul>\n

      The algorithm ends at this point and we have achieved a flow of 30, which is the maximum flow for this particular example.<\/p>\n

      There are two basic operations that was performed:<\/p>\n

        \n
      • we push a forward flow on edges with leftover capacity<\/li>\n
      • we push a backward flow on edges already carrying\u00a0 a flow<\/li>\n<\/ul>\n

         <\/p>\n

        2. Introduction to Residual Graphs<\/strong><\/p>\n

        A residual graph is defined on a flow network G which has a flow f as Gf<\/sub> of G with respect to f.\u00a0Gf<\/sub> is is defined as follows:<\/p>\n

          \n
        • The set of nodes in\u00a0Gf<\/sub> is the same as in G<\/li>\n
        • For each edge\u00a0 e = (u, v) of G, where f(e) < ce<\/sub>, there are ce<\/sub> – f(e)<\/strong> units which we can push forward by. So we include an edge e’ = (u, v) in\u00a0Gf<\/sub> \u00a0with capacity ce<\/sub> – f(e)<\/strong>. This is a forward edge in same direction as the original edge.<\/li>\n
        • For each edge of G,\u00a0 where f(e) > 0, there are f(e) units of flow that we can ‘push backward’ or undo. So we include and edge e’ = (u, v) in\u00a0 Gf<\/sub>\u00a0 with capacity of f(e)<\/strong>. These are in opposite direction to e and is a backward edge.<\/li>\n<\/ul>\n

          The residual graph for Figure 1 after 1d and after 1f is given in Figure 2.<\/p>\n

          \"\"
          Figure 1: Residual Graphs<\/figcaption><\/figure>\n

           <\/p>\n

          3. About Residual Graphs<\/strong><\/p>\n

          Each edge in the original graph G yields one or two edges in the residual graph\u00a0G<\/span>f<\/sub>. If 0 < f(e) < ce<\/sub>, then it would result in both a forward and a backward edge in the residual graph Gf<\/sub>. This also means that the number\u00a0 of edges in the residual graph is at most twice the number of edges in the original graph G.<\/p>\n

          The capacity of edges in the residual graph is called residual capacity.<\/p>\n

           <\/p>\n

          4. Augmenting Paths in a Residual Graph Using Bottleneck<\/strong><\/p>\n

          Now that we have built up the residual graph, we can then proceed to examine how to analyse it. That is how to push flows from s to t in the residual graph.\u00a0 Assuming that P is a simple path in\u00a0Gf\u00a0<\/sub>from s to t which means that P does not contain any loops. The we can define a term called bottleneck(P, f)<\/em> as the minimum residual capacity of any edge in P.<\/p>\n

          The bottleneck capacity is used to either increase or decrease the flows in the path P by the process of augmentation.<\/p>\n","protected":false},"excerpt":{"rendered":"

          We cover the following Introduction to Ford-Fulkerson Algorithm Introduction to Residual Graphs About Residual Graphs Augmenting Paths in Residual Graph Using Bottleneck 1. Introduction to … <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"pagelayer_contact_templates":[],"_pagelayer_content":"","footnotes":""},"categories":[414],"tags":[],"class_list":["post-1959","post","type-post","status-publish","format-standard","hentry","category-programming"],"_links":{"self":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/1959","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=1959"}],"version-history":[{"count":1,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/1959\/revisions"}],"predecessor-version":[{"id":2127,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/posts\/1959\/revisions\/2127"}],"wp:attachment":[{"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/media?parent=1959"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/categories?post=1959"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/kindsonthegenius.com\/blog\/wp-json\/wp\/v2\/tags?post=1959"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}