Network Flow Algorithms - Learn Step by Step

🎯 Why Network Flow Matters

Network flow algorithms solve critical real-world problems:

🚚 Transportation: Optimizing delivery routes and traffic flow
🌐 Internet: Managing data flow in networks
💼 Business: Supply chain optimization
⚡ Power Grids: Distributing electricity efficiently

💡 Real-World Example: When Netflix streams a movie to millions of users, network flow algorithms help determine the optimal paths for data to travel from servers to your device!

🌟 Network Flow Basics

What is a Flow Network?

A flow network is a directed graph where each edge has a capacity and we want to send maximum "flow" from source to sink.

Key Concepts

Source (S): Where flow originates
Sink (T): Where flow ends
Capacity: Maximum flow an edge can carry
Flow Conservation: Input = Output (except at S and T)

🎯 Ford-Fulkerson Algorithm

How It Works

Repeatedly find augmenting paths from source to sink and push flow through them.

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0] * vertices for _ in range(vertices)]
    
    def add_edge(self, u, v, capacity):
        self.graph[u][v] = capacity
    
    def bfs(self, source, sink, parent):
        """Find if there's a path from source to sink"""
        visited = [False] * self.V
        queue = [source]
        visited[source] = True
        
        while queue:
            u = queue.pop(0)
            
            for v in range(self.V):
                if not visited[v] and self.graph[u][v] > 0:
                    queue.append(v)
                    visited[v] = True
                    parent[v] = u
                    if v == sink:
                        return True
        
        return False
    
    def ford_fulkerson(self, source, sink):
        """Find maximum flow from source to sink"""
        parent = [-1] * self.V
        max_flow = 0
        
        while self.bfs(source, sink, parent):
            # Find minimum capacity along the path
            path_flow = float("inf")
            s = sink
            
            while s != source:
                path_flow = min(path_flow, self.graph[parent[s]][s])
                s = parent[s]
            
            # Update residual capacities
            v = sink
            while v != source:
                u = parent[v]
                self.graph[u][v] -= path_flow
                self.graph[v][u] += path_flow
                v = parent[v]
            
            max_flow += path_flow
        
        return max_flow

# Example usage
g = Graph(6)
g.add_edge(0, 1, 16)  # s -> a
g.add_edge(0, 2, 13)  # s -> b
g.add_edge(1, 2, 10)  # a -> b
g.add_edge(1, 3, 12)  # a -> c
g.add_edge(2, 1, 4)   # b -> a
g.add_edge(2, 4, 14)  # b -> d
g.add_edge(3, 2, 9)   # c -> b
g.add_edge(3, 5, 20)  # c -> t
g.add_edge(4, 3, 7)   # d -> c
g.add_edge(4, 5, 4)   # d -> t

print(f"Maximum flow: {g.ford_fulkerson(0, 5)}")
# Output: Maximum flow: 23

💡 Time Complexity: O(E × max_flow) where E is number of edges. With BFS (Edmonds-Karp), it becomes O(VE²).

💡 Real-World Applications

1. Bipartite Matching

Match items from one set to another (e.g., job assignments)

def max_bipartite_matching(graph, m, n):
    """
    Maximum matching in bipartite graph
    m: size of left set, n: size of right set
    """
    # Create flow network
    V = m + n + 2  # +2 for source and sink
    flow_graph = [[0] * V for _ in range(V)]
    
    # Connect source to left vertices
    for i in range(1, m + 1):
        flow_graph[0][i] = 1
    
    # Connect edges in bipartite graph
    for u in range(m):
        for v in graph[u]:
            flow_graph[u + 1][m + 1 + v] = 1
    
    # Connect right vertices to sink
    for i in range(m + 1, m + n + 1):
        flow_graph[i][V - 1] = 1
    
    # Run max flow
    g = Graph(V)
    g.graph = flow_graph
    return g.ford_fulkerson(0, V - 1)

# Example: Job assignment
job_graph = [
    [0, 1],     # Worker 0 can do jobs 0, 1
    [1, 2],     # Worker 1 can do jobs 1, 2
    [0, 2],     # Worker 2 can do jobs 0, 2
]
print(f"Maximum matching: {max_bipartite_matching(job_graph, 3, 3)}")

2. Minimum Cut

Find the minimum capacity cut that separates source from sink.

def find_min_cut(capacity, source, sink):
    """Find minimum s-t cut"""
    n = len(capacity)
    residual = [row[:] for row in capacity]
    
    # Run max flow
    g = Graph(n)
    g.graph = residual
    max_flow = g.ford_fulkerson(source, sink)
    
    # Find reachable vertices from source
    visited = [False] * n
    queue = [source]
    visited[source] = True
    
    while queue:
        u = queue.pop(0)
        for v in range(n):
            if not visited[v] and g.graph[u][v] > 0:
                visited[v] = True
                queue.append(v)
    
    # Find cut edges
    cut_edges = []
    for u in range(n):
        for v in range(n):
            if visited[u] and not visited[v] and capacity[u][v] > 0:
                cut_edges.append((u, v))
    
    return max_flow, cut_edges

3. Network Reliability

Application	Problem Type	Solution
Internet Routing	Max bandwidth	Max flow
Power Grid	Vulnerability	Min cut
Supply Chain	Bottleneck	Min cut
Task Assignment	Matching	Bipartite flow

🚀 Advanced Topics

Dinic's Algorithm

Faster algorithm using level graphs and blocking flows.

from collections import deque

class Dinic:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]
        self.level = [-1] * n
    
    class Edge:
        def __init__(self, to, rev, cap):
            self.to = to
            self.rev = rev
            self.cap = cap
    
    def add_edge(self, u, v, cap):
        """Add edge with capacity"""
        self.graph[u].append(self.Edge(v, len(self.graph[v]), cap))
        self.graph[v].append(self.Edge(u, len(self.graph[u]) - 1, 0))
    
    def bfs(self, source, sink):
        """Build level graph"""
        self.level = [-1] * self.n
        self.level[source] = 0
        queue = deque([source])
        
        while queue:
            v = queue.popleft()
            for edge in self.graph[v]:
                if self.level[edge.to] < 0 and edge.cap > 0:
                    self.level[edge.to] = self.level[v] + 1
                    queue.append(edge.to)
        
        return self.level[sink] >= 0
    
    def dfs(self, v, sink, flow):
        """Find blocking flow"""
        if v == sink:
            return flow
        
        for edge in self.graph[v]:
            if (self.level[v] < self.level[edge.to] and 
                edge.cap > 0):
                d = self.dfs(edge.to, sink, min(flow, edge.cap))
                if d > 0:
                    edge.cap -= d
                    self.graph[edge.to][edge.rev].cap += d
                    return d
        
        return 0
    
    def max_flow(self, source, sink):
        """Dinic's algorithm - O(V²E)"""
        flow = 0
        while self.bfs(source, sink):
            while True:
                f = self.dfs(source, sink, float('inf'))
                if f == 0:
                    break
                flow += f
        return flow

Push-Relabel Algorithm

Alternative approach that's often faster in practice for dense graphs.

Min Cost Max Flow

Find maximum flow with minimum cost when edges have costs.

💪 Practice Problems

Problem 1: Maximum Students in Exam

Medium

Given a classroom with broken seats, find maximum students that can take exam without cheating.

def max_students(seats):
    """
    seats[i][j] = '#' if broken, '.' if available
    Students can't sit adjacent or diagonally in front
    """
    # This becomes a maximum independent set problem
    # Convert to bipartite matching
    pass  # Implementation exercise

Problem 2: Project Selection

Hard

Select projects to maximize profit with dependencies.

def project_selection(projects, dependencies):
    """
    projects[i] = (profit, cost)
    dependencies[i] = [j, k, ...] means i depends on j, k, ...
    """
    n = len(projects)
    # Source = n, Sink = n + 1
    V = n + 2
    
    graph = [[0] * V for _ in range(V)]
    total_profit = 0
    
    for i, (profit, cost) in enumerate(projects):
        if profit > cost:
            # Profitable project
            graph[n][i] = profit - cost
            total_profit += profit - cost
        else:
            # Costly project
            graph[i][n + 1] = cost - profit
    
    # Add dependency edges
    for i, deps in enumerate(dependencies):
        for j in deps:
            graph[i][j] = float('inf')
    
    # Max profit = total profit - min cut
    g = Graph(V)
    g.graph = graph
    min_cut = g.ford_fulkerson(n, n + 1)
    
    return total_profit - min_cut

💡 Interview Tips:

Network flow = Think about source, sink, and capacities
Matching problems often reduce to flow
Min cut = Max flow (by duality)
Practice recognizing when to model as flow