Back to course

Exercise 4

Flow Algorithms

Network AnalysisAlgorithm ExecutionMedium Difficulty

Exam Format & Expectations

Flow algorithm questions typically ask you to:

  1. Execute algorithm steps - Run Ford-Fulkerson or Edmonds-Karp
  2. Find augmenting paths - BFS for shortest path in residual network
  3. Identify critical edges - Which edges become saturated?
  4. Calculate flow changes - How does flow change after augmentation?

Past Exam Example: Edmonds-Karp Execution (2024)

Given Network:

s → a: 10 | s → b: 10 | a → b: 2 | a → t: 8 | b → t: 10

Current flow f with value |f| = 10:

  • f(s,a) = 8, f(s,b) = 2
  • f(a,b) = 0, f(a,t) = 8
  • f(b,t) = 2

Question 4a: Find the shortest augmenting path in Gf

Full Solution(4/4)

Step 1: Construct residual network Gf:

Residual capacities:
• cf(s,a) = 10 - 8 = 2
• cf(s,b) = 10 - 2 = 8
• cf(a,b) = 2 - 0 = 2
• cf(a,t) = 8 - 8 = 0 (no edge)
• cf(b,t) = 10 - 2 = 8
• cf(a,s) = 8 (backward)
• cf(b,s) = 2 (backward)
• cf(b,a) = 0 (no edge)
• cf(t,a) = 8 (backward)
• cf(t,b) = 2 (backward)

Step 2: Run BFS from s to t:

Shortest augmenting path: s a b t

Bottleneck capacity: min{2, 2, 8} = 2

Question 4b: Which edges become critical after augmentation?

Full Solution(3/3)

Definition: An edge is critical if it becomes saturated (residual capacity = 0) after augmentation.

After augmenting by 2 units along s → a → b → t:

  • f'(s,a) = 8 + 2 = 10 cf'(s,a) = 0 ✓ Critical
  • f'(a,b) = 0 + 2 = 2 cf'(a,b) = 0 ✓ Critical
  • f'(b,t) = 2 + 2 = 4 cf'(b,t) = 6 ✗ Not critical

Answer: Edges (s,a) and (a,b) become critical.

Question 4c: What is the new inflow at vertex b after augmentation?

Full Solution(3/3)

Definition: inflow(v) = Σu f(u,v)

After augmentation:

  • f'(s,b) = 2 (unchanged)
  • f'(a,b) = 2 (increased from 0)

inflow(b) = f'(s,b) + f'(a,b) = 2 + 2 = 4

Key Concepts to Master

Residual Network

For each edge (u,v) with capacity c and flow f:

  • • Forward: cf(u,v) = c(u,v) - f(u,v)
  • • Backward: cf(v,u) = f(u,v)

Only include edges with positive residual capacity!

Critical Edges

  1. 1. Find all residual capacities on path
  2. 2. Bottleneck = minimum capacity
  3. 3. Critical = edges with capacity = bottleneck
  4. 4. Can have multiple critical edges!

Inflow Analysis

inflow(v) = Σu f(u,v)

After augmentation:

• Check each vertex on path

• Account for reversed edges

Algorithm Differences

Edmonds-Karp:

• Uses BFS for shortest path

• O(VE²) time complexity

Ford-Fulkerson:

• Any augmenting path

• May not terminate with irrational capacities

Common Mistakes to Avoid

Calculation Errors

  • • Using original network instead of residual
  • • Forgetting backward edges exist
  • • Wrong residual capacity formula
  • • Missing some critical edges

Conceptual Errors

  • • Confusing flow value with edge flow
  • • Not checking all paths for alternatives
  • • Assuming unique shortest path
  • • Forgetting capacity constraints

Pro tip: Always draw the residual network clearly. Label each edge with its residual capacity. This prevents most errors.