Vincec's Dimension

Algorithm Review Notes - Network Flow

Word count: 624 / Reading time: 4 min
2018/11/25 Share

Network Flow ref

Limiation of Network Flow

  • Capacity Law(Constraints)
    • O <= f(e) <= c(e)
  • Conservation Law
    • flow in = flow out
    • sum(f(e in to v)) = sum(f(e out of v))


Given a flow network G, find a flow f from s to t of the maximum possible value.

Residual Graph Gf

  • Forward Edges
  • Backward Edges

Network: G = (V, E) and flow f
Residual capacity: cf(e) = c(e) - f(e)
Residual Graph: Gf(V, Ef), where Ef = {e| f(e) < c(e)}(forward edge){eR| f(e) > 0}(backward edge)

Augmenting Path 增广路径

Path in the Gf

Bottleneck(P, f): the smallest capacity in Gf on any edge of P.

Cuts check

Cuts Capacity

cap(A, B) = sum of c(e out of A)

Min Cut

  • Minimum cut = the cut in the network that has the smallest possible capacity
  • Minimum cut capacity = the capacity of the minimum cut

Cuts and Flow

  • |f| = sum of (flow-out of A) - sum of (flow-in of A) = sum of f(e out of source)
  • Maximum flow ≤ capacity of any cut
  • Maximum flow = Capacity of the min. cut of the network

Max-flow, Min-cut theorem

Value of Maxi-flow = Capacity of the min-cut

  • the construct yields a cut: S ∈ X, T ∉ X, there is T ∈ Y
  • For each forward edge e in the cut C: f(e) = c(e)
  • For each backward edge e in the cut C: f(e) = 0

Ford-Fulkerson Algorithm

  • Given(G, s, t, c) [Graph, source S, sink T, capacity]
  • Start with |f| = 0, f(e) = 0, [set the start flow]
  • Find an augmenting path, [by using dfs]
  • Augment flow along this path
  • Repeat until no an s-t path in the Gf, [by proving of min cuts, repeat times will exceed the edge number due to residual graph]

Runtime Complexity

  • Total number of iterations: |f|
  • Each augmentation increases value of flow by at least 1
  • Running iterations: O(E + V)
  • Total runtime: O(|f|*(E + V)), pseudo-polynomial, input size: |f|

Edmonds-Karp Algorithm

By using BFS instead of DFS, Find an shortest augmenting path

Runtime Complexity

O(V*E2), polynomial

Capacity-Scaling Algoritm

  • The bottleneck capacity if an augmenting path is the minmum residual capacity of any edge in the path
  • Choosing augmenting path with highest bottleneck capacity

Runtime Complexity

O(E2 ㏒|f|), weakly-polynomial, because the input size is ㏒|f|

Network Flow Problems - S-T Flow 源匯流

  • Bipartite Graph (translation problem)
  • Rook Attack
  • Edge Disjoint Paths (do not share any edge, but ok with same vertex)
  • Edge Disjoint Paths in Undirected Graphs
  • Vertex Disjoint Paths (do not share any vertex, edge either of casuse)
  • Image Segmentation (to find the maximum, by using whole minus the min-cut)

Circulation with Demands - Flow 循環流

Circulation (having s-t flow as well as t-s flow, used in supply and demand, to find a feasible) _[ref1][ref2] [ref3]_

  • total supply(positive on the node) = total demand(negative on the node)
  • capacity constraint (0 <= flow <= cap)
  • demand constraint ( flow in - flow out = node demand)


  • Remove demands (By adding s-t)
  • Calculate using FF
  • replace demans (By removing s-t)

Circulation with Demands and lower Bounds

Want to force flow have flow between two given nodes, need to change the Capacity Constraint with that lower bound, to find a feasible [ref4]:

  • Capacity Constraint: l(e) <= f(e) <= c(e)


  • Remove Lower bound [lower, upper], by changing the each node demands
    • L(v) = f0in(v) - f0out(v) = sum(l(e to v)) - sum(l(e out to v))
    • compute L(node)
  • Remove demands (By adding s-t)
  • Calculate using FF
  • replace demands (By removing s-t)


  • slides
  1. 1. Network Flow ref
    1. 1.1. Limiation of Network Flow
    2. 1.2. Max-flow
      1. 1.2.1. Residual Graph Gf
        1. Augmenting Path 增广路径
      2. 1.2.2. Cuts check
        1. Cuts Capacity
      3. 1.2.3. Min Cut
        1. Cuts and Flow
        2. Max-flow, Min-cut theorem
      4. 1.2.4. Ford-Fulkerson Algorithm
        1. Runtime Complexity
      5. 1.2.5. Edmonds-Karp Algorithm
        1. Runtime Complexity
      6. 1.2.6. Capacity-Scaling Algoritm
        1. Runtime Complexity
    3. 1.3. Network Flow Problems - S-T Flow 源匯流
    4. 1.4. Circulation with Demands - Flow 循環流
      1. Steps:
    5. 1.4.1. Circulation with Demands and lower Bounds
      1. Steps:
  • 2. Reference