Max Flow (Dinic's Algorithm)

Dinic's Algorithm สำหรับหา Maximum Flow ใน Network

Dinic’s Algorithm

Dinic’s Algorithm เป็น algorithm สำหรับหา Maximum Flow ใน flow network โดยมี time complexity $O(V^2 E)$ และ $O(E \sqrt{V})$ สำหรับ unit capacity graphs

Flow Network

Source $s$ : จุดเริ่มต้นของ flow
Sink $t$ : จุดสิ้นสุดของ flow
Capacity $c(u, v)$ : ความจุสูงสุดของ edge $(u, v)$
Flow $f(u, v)$ : ปริมาณ flow บน edge $(u, v)$

แนวคิดหลัก

BFS สร้าง level graph (เก็บ distance จาก source)
DFS หา blocking flow ใน level graph
ทำซ้ำจนไม่มี augmenting path

Implementation

struct Dinic {
    struct Edge {
        int to, rev;
        long long cap;
    };
    
    int n;
    vector<vector<Edge>> graph;
    vector<int> level, iter;
    
    Dinic(int n) : n(n), graph(n), level(n), iter(n) {}
    
    void addEdge(int from, int to, long long cap) {
        graph[from].push_back({to, (int)graph[to].size(), cap});
        graph[to].push_back({from, (int)graph[from].size() - 1, 0});
    }
    
    // Bidirectional edge (for undirected graphs)
    void addBidirectionalEdge(int from, int to, long long cap) {
        graph[from].push_back({to, (int)graph[to].size(), cap});
        graph[to].push_back({from, (int)graph[from].size() - 1, cap});
    }
    
    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            
            for (auto& e : graph[u]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[u] + 1;
                    q.push(e.to);
                }
            }
        }
        
        return level[t] >= 0;
    }
    
    long long dfs(int u, int t, long long f) {
        if (u == t) return f;
        
        for (int& i = iter[u]; i < graph[u].size(); i++) {
            Edge& e = graph[u][i];
            
            if (e.cap > 0 && level[u] < level[e.to]) {
                long long d = dfs(e.to, t, min(f, e.cap));
                
                if (d > 0) {
                    e.cap -= d;
                    graph[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        
        return 0;
    }
    
    long long maxFlow(int s, int t) {
        long long flow = 0;
        
        while (bfs(s, t)) {
            fill(iter.begin(), iter.end(), 0);
            
            long long f;
            while ((f = dfs(s, t, LLONG_MAX)) > 0) {
                flow += f;
            }
        }
        
        return flow;
    }
};

ตัวอย่างการใช้งาน

int main() {
    int n, m;
    cin >> n >> m;
    
    Dinic dinic(n);
    
    for (int i = 0; i < m; i++) {
        int u, v;
        long long c;
        cin >> u >> v >> c;
        dinic.addEdge(u, v, c);
    }
    
    int source = 0, sink = n - 1;
    cout << dinic.maxFlow(source, sink) << endl;
    
    return 0;
}

ทฤษฎีที่เกี่ยวข้อง

Max-Flow Min-Cut Theorem

$\text{Maximum Flow} = \text{Minimum Cut}$

Minimum Cut คือ set of edges ที่มี total capacity น้อยที่สุดที่เมื่อลบออกแล้วไม่มี path จาก $s$ ไป $t$

หา Minimum Cut

vector<pair<int, int>> minCut(int s, int t) {
    maxFlow(s, t);
    
    // BFS from source in residual graph
    vector<bool> visited(n, false);
    queue<int> q;
    q.push(s);
    visited[s] = true;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (auto& e : graph[u]) {
            if (e.cap > 0 && !visited[e.to]) {
                visited[e.to] = true;
                q.push(e.to);
            }
        }
    }
    
    // Edges crossing the cut
    vector<pair<int, int>> cutEdges;
    for (int u = 0; u < n; u++) {
        if (visited[u]) {
            for (auto& e : graph[u]) {
                if (!visited[e.to] && e.cap == 0) {
                    cutEdges.push_back({u, e.to});
                }
            }
        }
    }
    
    return cutEdges;
}

ประยุกต์ใช้งาน

1. Bipartite Matching

ใช้ max flow โดย:

เพิ่ม source $s$ เชื่อมไปยัง nodes ฝั่งซ้าย (capacity 1)
เพิ่ม sink $t$ เชื่อมจาก nodes ฝั่งขวา (capacity 1)
Edges ระหว่าง 2 ฝั่งมี capacity 1

int bipartiteMatching(int leftSize, int rightSize, vector<pair<int,int>>& edges) {
    Dinic dinic(leftSize + rightSize + 2);
    int s = leftSize + rightSize;
    int t = s + 1;
    
    // Connect source to left
    for (int i = 0; i < leftSize; i++) {
        dinic.addEdge(s, i, 1);
    }
    
    // Connect right to sink
    for (int i = 0; i < rightSize; i++) {
        dinic.addEdge(leftSize + i, t, 1);
    }
    
    // Add edges between left and right
    for (auto& [u, v] : edges) {
        dinic.addEdge(u, leftSize + v, 1);
    }
    
    return dinic.maxFlow(s, t);
}

2. Edge-Disjoint Paths

จำนวน edge-disjoint paths จาก $s$ ไป $t$ = max flow (capacity 1 ทุก edge)

3. Vertex-Disjoint Paths

แยกแต่ละ vertex $v$ เป็น $v_{in}$ และ $v_{out}$ เชื่อมด้วย edge capacity 1

4. Project Selection Problem

ปัญหาเลือก projects ที่มี dependencies และ profits/costs

Complexity

Graph Type	Time Complexity
General	$O(V^2 E)$
Unit capacity	$O(E \sqrt{V})$
Unit network (bipartite)	$O(E \sqrt{V})$

เปรียบเทียบ Max Flow Algorithms

Algorithm	Time Complexity	Best For
Ford-Fulkerson	$O(E \cdot maxFlow)$	Small flows
Edmonds-Karp	$O(VE^2)$	General
Dinic	$O(V^2 E)$	General, bipartite
Push-Relabel	$O(V^2 E)$ หรือ $O(V^3)$	Dense graphs

Tips

iter array - Dinic’s optimization ไม่ revisit edges ที่ถูก block แล้วใน phase เดียวกัน
Unit capacity - Dinic เร็วมากสำหรับ bipartite matching
Scaling - สำหรับ capacity ใหญ่ อาจใช้ capacity scaling
Multiple sources/sinks - เพิ่ม super source/sink