Thi đấu

Luồng Cực Đại Trên Mạng: Thuật Toán Edmonds-Karp và Dinic

Giải bài toán luồng cực đại trên mạng bằng hai thuật toán tiêu biểu Edmonds-Karp O(V*E^2) và Dinic O(V^2*E) thông qua đường tăng luồng và đồ thị phân tầng.

Luồng Cực Đại Trên Mạng: Thuật Toán Edmonds-Karp và Dinic

Trong thế giới thuật toán đồ thị, Bài toán Luồng cực đại trên mạng (Maximum Network Flow) là một trong những bài toán đẹp đẽ và có tính ứng dụng sâu rộng nhất. Từ bài toán điều phối lưu lượng giao thông đường bộ, tối ưu hóa băng thông mạng internet, sắp xếp ca làm việc cho nhân viên, cho đến bài toán ghép cặp nhiều đôi nhất trên đồ thị hai phía và lát cắt hình ảnh trong thị giác máy tính, tất cả đều có thể mô hình hóa về mạng luồng.

Hai cột mốc quan trọng nhất trong lịch sử giải quyết bài toán luồng cực đại là thuật toán Edmonds-Karp (1972) và thuật toán Dinic (do nhà toán học Yefim Dinitz phát minh năm 1970). Trong khi Edmonds-Karp là bước đệm lý thuyết dễ hiểu với độ phức tạp \(O(V \cdot E^2)\), thì thuật toán Dinic với tư duy đồ thị phân tầng (Level Graph) và con trỏ cạnh nghẽn (Blocking Flow) đạt tốc độ vượt trội \(O(V^2 \cdot E)\), đặc biệt đạt \(O(E \sqrt{V})\) trên mạng đơn vị — trở thành chuẩn mực bắt buộc trong các kỳ thi Học sinh giỏi Quốc gia (VOI) và ACM/ICPC.

Bài viết này sẽ phân tích toàn diện định lý lát cắt hẹp nhất (Max-Flow Min-Cut Theorem), cấu trúc mạng thặng dư (Residual Graph), và hướng dẫn chi tiết cách cài đặt thuật toán Dinic tối ưu.

1. Các khái niệm cốt lõi của mạng luồng

Một mạng luồng \(G = (V, E)\) là một đồ thị có hướng thỏa mãn:

  1. Mỗi cạnh \((u, v) \in E\) có một dung lượng không âm \(c(u, v) \ge 0\) (Capacity).
  2. Tồn tại hai đỉnh đặc biệt: đỉnh phát \(S\) (Source - nguồn cấp luồng) và đỉnh thu \(T\) (Sink - nơi nhận luồng).
  3. Luồng trên mỗi cạnh \(f(u, v)\) phải thỏa mãn hai điều kiện nghiêm ngặt:
    • Giới hạn dung lượng: \(0 \le f(u, v) \le c(u, v)\).
    • Bảo toàn luồng: Đối với mọi đỉnh \(u\) khác \(S\) và \(T\), tổng luồng đi vào đỉnh \(u\) phải bằng tổng luồng đi ra khỏi đỉnh \(u\): \[\sum_{v} f(v, u) = \sum_{w} f(u, w)\]

Tổng giá trị luồng của mạng là tổng lượng luồng đi ra khỏi đỉnh nguồn \(S\): \[|f| = \sum_{v} f(S, v)\]

Luồng Cực Đại Trên Mạng (Max-Flow) & Thuật Toán Dinic O(V^2 E) Xây dựng đồ thị phân tầng bằng BFS và tìm đường tăng luồng nghẽn bằng DFS kèm con trỏ ptr So sánh Edmonds-Karp vs Dinic • Edmonds-Karp: BFS từng đường tăng luồng O(V E^2) • Dinic: BFS phân tầng + DFS đẩy đa luồng O(V^2 E) • Mạng đơn vị: Dinic chạy O(E√V) Kỹ thuật con trỏ ptr[u]: Không bao giờ xét lại các cạnh đã đầy dung lượng Mỗi pha tìm luồng nghẽn trong O(V·E) Chạy tay mạng luồng 4 đỉnh (S=0, T=3) Cạnh: 0->1(10), 0->2(10), 1->2(2), 1->3(4), 2->3(9) Pha 1, DFS lần 1: 0 -> 1 -> 3 đẩy +4 (cạnh 1->3 đầy) Pha 1, DFS lần 2: 0 -> 2 -> 3 đẩy +9 (cạnh 2->3 đầy) Kết quả luồng cực đại: Max Flow = 4 + 9 = 13 Định lý Max-Flow Min-Cut: Lát cắt hẹp nhất = 13
Luồng Cực Đại Dinic Thuật toán phân tầng O(V^2 E) Cấu trúc 2 pha: 1. BFS gán level[u] khoảng cách từ S 2. DFS tìm luồng nghẽn theo level[v] = level[u]+1 Mảng ptr[u] tối ưu loại bỏ cạnh bão hòa Ví dụ mạng 4 đỉnh: Đường 0->1->3 : đẩy 4 Đường 0->2->3 : đẩy 9 => Tổng luồng cực đại = 13 Bằng dung lượng lát cắt nhỏ nhất Min-Cut
Mô hình mạng luồng 4 đỉnh: thuật toán Dinic tìm hai đường tăng luồng (+4 và +9) ngay trong pha đầu tiên, đạt luồng cực đại 13; lần BFS thứ hai không còn tới được đỉnh thu.

Mạng thặng dư và Cạnh đảo (Residual Graph & Back-Edges)

Để cho phép thuật toán "sửa sai" bằng cách hủy bớt luồng đã đẩy qua một cạnh nếu sau đó tìm thấy đường đi tốt hơn, với mỗi cạnh có hướng \(u \to v\) dung lượng \(c\), ta luôn thêm một cạnh đảo ngược \(v \to u\) có dung lượng ban đầu bằng 0.

Dung lượng thặng dư còn lại trên cạnh được định nghĩa:

  • \(c_f(u, v) = c(u, v) - f(u, v)\) (dung lượng có thể đẩy thêm).
  • \(c_f(v, u) = f(u, v)\) (dung lượng có thể hủy bớt luồng đi ngược lại).

Định lý Luồng cực đại - Lát cắt cực tiểu (Max-Flow Min-Cut Theorem)

Một lát cắt \((S, T)\) là một cách phân chia tập đỉnh \(V\) thành hai tập rời nhau \(A\) và \(B\) sao cho \(S \in A\) và \(T \in B\). Dung lượng của lát cắt là tổng dung lượng các cạnh đi từ \(A\) sang \(B\): \[C(A, B) = \sum_{u \in A, v \in B} c(u, v)\]

Định lý nổi tiếng của Ford-Fulkerson khẳng định rằng:

Giá trị luồng cực đại từ \(S\) đến \(T\) luôn bằng chính xác dung lượng của lát cắt hẹp nhất (Min-Cut) phân tách \(S\) và \(T\).

2. So sánh thuật toán Edmonds-Karp và Dinic

Thuật toán Edmonds-Karp (O(V * E^2))

Edmonds-Karp là dạng hiện thực hóa của phương pháp Ford-Fulkerson: ở mỗi bước, thuật toán chạy BFS tìm đường đi ngắn nhất (ít cạnh nhất) có dung lượng thặng dư lớn hơn 0 từ \(S\) đến \(T\). Sau đó, đẩy lượng luồng tối đa có thể trên đường đi đó và cập nhật lại mạng thặng dư. Lặp lại quá trình cho đến khi không còn đường tăng luồng từ \(S\) đến \(T\).

Mặc dù đúng đắn, Edmonds-Karp phải chạy lại toàn bộ BFS cho từng đường tăng luồng đơn lẻ, khiến nó quá chậm khi đồ thị có hàng nghìn đỉnh.

Thuật toán Dinic (O(V^2 * E))

Thuật toán Dinic tạo ra một bước đột phá bằng cách chia nhỏ quá trình tăng luồng thành các Pha (Phases); mỗi pha gồm các bước:

  1. Bước 1 (Xây dựng đồ thị phân tầng bằng BFS): Chạy BFS từ \(S\) để gán nhãn khoảng cách level[u] cho mỗi đỉnh \(u\). Nếu không tới được \(T\) (level[T] == -1), thuật toán dừng lại ngay lập tức!
  2. Bước 2 (Đẩy luồng nghẽn bằng DFS): Dùng DFS đẩy luồng dọc theo các cạnh thỏa mãn điều kiện tiến bậc nghiêm ngặt: \[\text{level}[v] == \text{level}[u] + 1 \quad \text{và} \quad c_f(u, v) > 0\]
  3. Tối ưu hóa con trỏ cạnh ptr[u]: Trong quá trình DFS, một đỉnh \(u\) có thể được ghé thăm nhiều lần bởi các nhánh khác nhau. Để tránh duyệt lại các cạnh kề đã bị bão hòa hoặc không thể dẫn tới \(T\), ta duy trì một mảng con trỏ ptr[u] trỏ tới cạnh kề tiếp theo chưa xét. Tối ưu này đảm bảo mỗi cạnh bão hòa chỉ bị duyệt qua đúng một lần trong mỗi pha!
Học cùng giảng viên

Chủ đề này nằm trong Buổi 15 - Max Flow / Bipartite Matching của Tài năng lập trình. Xem đề cương

3. Cài đặt C++17 và Python 3 chuẩn thi đấu

Dưới đây là khung cài đặt thuật toán Dinic chuẩn mực, cấu trúc rõ ràng và tốc độ tối đa:

Cài đặt C++17

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const long long INF = 1e18;

struct Edge {
    int to;
    long long cap;
    long long flow;
    int rev; // Chi so cua canh dao trong danh sach ke cua dinh 'to'
};

struct Dinic {
    int n;
    vector<vector<Edge>> adj;
    vector<int> level;
    vector<int> ptr;

    Dinic(int n) : n(n), adj(n), level(n), ptr(n) {}

    // Them canh co huong tu 'from' den 'to' voi dung luong 'cap'
    void add_edge(int from, int to, long long cap) {
        adj[from].push_back({to, cap, 0, (int)adj[to].size()});
        adj[to].push_back({from, 0, 0, (int)adj[from].size() - 1});
    }

    // BFS xay dung do thi phan tang
    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        level[s] = 0;
        queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (auto& edge : adj[v]) {
                if (edge.cap - edge.flow > 0 && level[edge.to] == -1) {
                    level[edge.to] = level[v] + 1;
                    q.push(edge.to);
                }
            }
        }
        return level[t] != -1;
    }

    // DFS day luong nghen kem con tro ptr
    long long dfs(int v, int t, long long pushed) {
        if (pushed == 0 || v == t) return pushed;
        for (int& cid = ptr[v]; cid < (int)adj[v].size(); ++cid) {
            auto& edge = adj[v][cid];
            int tr = edge.to;
            if (level[v] + 1 != level[tr] || edge.cap - edge.flow == 0) continue;
            long long push = dfs(tr, t, min(pushed, edge.cap - edge.flow));
            if (push == 0) continue;
            edge.flow += push;
            adj[tr][edge.rev].flow -= push;
            return push;
        }
        return 0;
    }

    // Tinh tong luong cuc dai tu s den t
    long long max_flow(int s, int t) {
        long long flow = 0;
        while (bfs(s, t)) {
            fill(ptr.begin(), ptr.end(), 0);
            while (long long pushed = dfs(s, t, INF)) {
                flow += pushed;
            }
        }
        return flow;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // Mang 4 dinh: 0 la Source, 3 la Sink
    Dinic dinic(4);
    dinic.add_edge(0, 1, 10);
    dinic.add_edge(0, 2, 10);
    dinic.add_edge(1, 2, 2);
    dinic.add_edge(1, 3, 4);
    dinic.add_edge(2, 3, 9);
    
    cout << dinic.max_flow(0, 3) << '\n'; // Ket qua: 13
    return 0;
}

Cài đặt Python 3

import sys
from collections import deque

INF = 10**18

class Edge:
    def __init__(self, to, cap, flow, rev):
        self.to = to
        self.cap = cap
        self.flow = flow
        self.rev = rev

class Dinic:
    def __init__(self, n):
        self.n = n
        self.adj = [[] for _ in range(n)]
        self.level = [-1] * n
        self.ptr = [0] * n

    def add_edge(self, from_node, to_node, cap):
        self.adj[from_node].append(Edge(to_node, cap, 0, len(self.adj[to_node])))
        self.adj[to_node].append(Edge(from_node, 0, 0, len(self.adj[from_node]) - 1))

    def bfs(self, s, t):
        self.level = [-1] * self.n
        self.level[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for edge in self.adj[v]:
                if edge.cap - edge.flow > 0 and self.level[edge.to] == -1:
                    self.level[edge.to] = self.level[v] + 1
                    q.append(edge.to)
        return self.level[t] != -1

    def dfs(self, v, t, pushed):
        if pushed == 0 or v == t:
            return pushed
        while self.ptr[v] < len(self.adj[v]):
            edge = self.adj[v][self.ptr[v]]
            tr = edge.to
            if self.level[v] + 1 == self.level[tr] and edge.cap - edge.flow > 0:
                push = self.dfs(tr, t, min(pushed, edge.cap - edge.flow))
                if push > 0:
                    edge.flow += push
                    self.adj[tr][edge.rev].flow -= push
                    return push
            self.ptr[v] += 1
        return 0

    def max_flow(self, s, t):
        flow = 0
        while self.bfs(s, t):
            self.ptr = [0] * self.n
            while True:
                pushed = self.dfs(s, t, INF)
                if pushed == 0:
                    break
                flow += pushed
        return flow

def main():
    dinic = Dinic(4)
    dinic.add_edge(0, 1, 10)
    dinic.add_edge(0, 2, 10)
    dinic.add_edge(1, 2, 2)
    dinic.add_edge(1, 3, 4)
    dinic.add_edge(2, 3, 9)
    print(dinic.max_flow(0, 3))

if __name__ == '__main__':
    main()

4. Ứng dụng quy đổi về bài toán mạng luồng

Khả năng mô hình hóa bài toán về mạng luồng là thước đo trình độ của một thí sinh giỏi:

  1. Bài toán cặp ghép cực đại trên đồ thị hai phía: Tạo đỉnh nguồn \(S\) nối tới mọi đỉnh tập trái với dung lượng 1; mọi đỉnh tập phải nối tới đỉnh thu \(T\) với dung lượng 1; các cạnh ban đầu có hướng từ trái sang phải với dung lượng 1. Luồng cực đại chính là số cặp ghép lớn nhất!
  2. Bài toán lát cắt hẹp nhất (Min-Cut): Sau khi chạy Dinic, các đỉnh \(u\) còn tới được từ \(S\) trong mạng thặng dư (level[u] != -1) tạo thành tập \(A\); các đỉnh còn lại tạo thành tập \(B\). Các cạnh nối từ \(A\) sang \(B\) ban đầu chính là lát cắt cực tiểu.
  3. Bài toán luồng có chặn dưới (Flow with Demands): Khi mỗi cạnh có yêu cầu \(l(e) \le f(e) \le c(e)\), ta biến đổi bằng cách trừ chặn dưới và đưa về bài toán luồng tiêu chuẩn.

Bảng chạy tay chi tiết từng pha thuật toán Dinic

Xét mạng luồng gồm 4 đỉnh \(\{S, 1, 2, T\}\) với nguồn \(S=0\), đích \(T=3\): Cạnh: \((0 \to 1, \text{cap}=10), (0 \to 2, \text{cap}=5), (1 \to 2, \text{cap}=15), (1 \to 3, \text{cap}=10), (2 \to 3, \text{cap}=10)\).

Pha Hành động Đồ thị phân tầng level Đường tăng luồng tìm được qua DFS Luồng tăng Luồng tích lũy
Pha 1: BFS Phân tầng từ nguồn \(S\) level = [0, 1, 1, 2] Đường \(0 \to 1 \to 3\) (nút thắt 10) \(+10\) 10
Pha 1: DFS Tìm tiếp trên đồ thị tầng level giữ nguyên Đường \(0 \to 2 \to 3\) (nút thắt 5) \(+5\) 15
Pha 2: BFS Phân tầng lại từ nguồn \(S\) Cạnh \(0 \to 1, 0 \to 2\) đã bão hòa Không còn đường từ \(S\) tới \(T\) 0 15 (Cực đại)

Tổng luồng cực đại đạt 15. Thuật toán kết thúc chỉ sau đúng 2 pha BFS!

Bốn cạm bẫy sống còn khi cài đặt thuật toán Dinic

  1. Quên tạo cạnh ngược với dung lượng ban đầu bằng 0: Mỗi khi thêm cạnh \((u, v)\) với dung lượng \(C\), bắt buộc phải thêm cạnh ngược \((v, u)\) với dung lượng 0. Trong đồ thị thặng dư, cạnh ngược cho phép "hủy luồng" khi cần thiết để tìm lời giải tối ưu toàn cục.

  2. Không cập nhật con trỏ ptr[u] trong hàm DFS: Con trỏ ptr[u] lưu chỉ số cạnh đang xét dở của đỉnh \(u\). Nếu không dùng con trỏ này, mỗi lần DFS lại duyệt từ cạnh đầu tiên của danh sách kề, làm mất bảo đảm \(O(V \cdot E)\) cho mỗi pha: DFS có thể duyệt lại cùng một nhánh cụt rất nhiều lần, thời gian có thể tăng theo hàm mũ và gây TLE.

  3. Tràn số luồng kiểu 32-bit: Trong các bài toán mạng luồng, tổng luồng cực đại có thể vượt quá \(2 \times 10^9\) ngay cả khi dung lượng mỗi cạnh là số vừa phải. Luôn sử dụng kiểu dữ liệu long long cho biến luồng flow và dung lượng cap.

  4. Tìm tập lát cắt cực tiểu (Min-Cut): Để tìm lát cắt cực tiểu sau khi luồng đã cực đại, duyệt BFS từ đỉnh nguồn \(S\) trên đồ thị thặng dư (chỉ đi qua cạnh có \(cap - flow > 0\)). Tập các đỉnh thăm được chính là tập \(S_{cut}\). Các cạnh ban đầu đi từ \(S_{cut}\) sang phần còn lại chính là các cạnh thuộc lát cắt cực tiểu.

Luyện ngay trên Big-O Coding

Để làm chủ kỹ thuật dựng đồ thị luồng và tối ưu Dinic, hãy thực hành ngay bài tập sau:

Tại sao trên mạng đơn vị (Unit Network), thuật toán Dinic lại chạy cực nhanh O(E sqrt(V))?

Trong mạng đơn vị (mỗi đỉnh trừ \(S, T\) chỉ có dung lượng vào hoặc dung lượng ra bằng 1), sau \(\sqrt{V}\) pha BFS đầu tiên, khoảng cách từ \(S\) đến \(T\) tăng lên ít nhất \(\sqrt{V}\). Do tổng số đỉnh là \(V\), số pha BFS tối đa còn lại không thể vượt quá \(2 \sqrt{V}\). Mỗi pha DFS chỉ duyệt qua các cạnh đơn vị trong \(O(E)\), do đó tổng độ phức tạp đạt \(O(E \sqrt{V})\). Đây là lý do Dinic vượt trội hơn hẳn thuật toán Kuhn trên đồ thị hai phía lớn.

Làm thế nào để tìm tập các cạnh thuộc lát cắt cực tiểu Min-Cut?

Sau khi hàm max_flow kết thúc, ta thực hiện một lượt duyệt BFS/DFS đơn giản từ đỉnh nguồn \(S\) chỉ đi qua các cạnh có \(edge.cap - edge.flow > 0\). Đánh dấu toàn bộ các đỉnh thăm được vào tập \(S_{\text{cut}}\). Tập các cạnh ban đầu có đỉnh đầu thuộc \(S_{\text{cut}}\) và đỉnh cuối không thuộc \(S_{\text{cut}}\) chính là các cạnh thuộc lát cắt cực tiểu.

Nguồn tham khảo

Muốn học bài bản cùng giảng viên?

Lộ trình 4 cấp độ cho học sinh thi Tin học trẻ, Chuyên Tin, Olympic, ACM-ICPC: xếp lớp theo năng lực, mini contest, lớp Đội tuyển. Học online, phí theo tháng.

Xem Tài năng lập trình

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483