Cấu trúc dữ liệu và Giải thuật Bài 111: Luồng cực đại (Max Flow - Ford-Fulkerson & Edmonds-Karp) - Giải quyết bài toán tối ưu lưu lượng qua mạng lưới đường ống.

Sau khi đã phân rã các cấu trúc đồ thị phức tạp bằng thuật toán Tarjan SCC ở Bài 110, chúng ta bước sang một nhánh tối ưu hóa đồ thị mang tính ứng dụng thực tế cực cao: Bài toán Luồng cực đại (Maximum Flow Problem).

Trong kiến trúc hạ tầng mạng và hệ thống phân tán, các bài toán sau đây đều quy về cùng một bản chất:

• Băng thông mạng (Network Bandwidth): Làm thế nào để truyền tải lượng dữ liệu lớn nhất từ máy chủ nguồn (Source) đến máy chủ đích (Sink) qua các trạm trung chuyển có giới hạn băng thông đường truyền?

• Hệ thống Logistics & Chuỗi cung ứng: Tối ưu hóa lưu lượng vận chuyển hàng hóa qua các kho bãi và tuyến đường giao nhận có tải trọng giới hạn.

• Cân bằng tải (Load Balancing): Phân phối lượng request tối đa từ client đến các cụm server xử lý mà không làm quá tải bất kỳ nút nào.

Để giải quyết triệt để các bài toán này, các nhà khoa học máy tính đã phát triển mô hình Luồng cực đại cùng hai thuật toán kinh điển: Ford-Fulkerson và phiên bản tối ưu hóa của nó bằng BFS — Edmonds-Karp.

1. Các định nghĩa nền tảng trong Mạng luồng (Flow Network)

Một Mạng luồng là một đồ thị có hướng $G = (V, E)$ trong đó mỗi cạnh $(u, v)$ có một Dung lượng tối đa (Capacity - $c(u, v)$):

1. Nguồn (Source - $s$): Điểm khởi phát luồng (nơi sản sinh dữ liệu/hàng hóa).

2. Đích (Sink - $t$): Điểm thu nhận luồng cuối cùng.

3. Điều kiện bảo toàn luồng (Flow Conservation): Tại mọi đỉnh trung gian (không phải $s$ và $t$), tổng lượng lưu lượng đi vào phải bằng tổng lượng lưu lượng đi ra.

4. Giới hạn dung lượng: Lưu lượng chạy qua bất kỳ cạnh nào không bao giờ được vượt quá dung lượng tối đa của cạnh đó ($f(u, v) \le c(u, v)$).

2. Ý tưởng cốt lõi: Đồ thị thặng dư (Residual Graph) & Đường tăng luồng (Augmenting Path)

Thuật toán Ford-Fulkerson hoạt động theo phương pháp lặp:

1. Tìm một Đường tăng luồng (Augmenting Path) từ $s$ đến $t$ trên đồ thị mà các cạnh vẫn còn dung lượng trống (thặng dư > 0).

2. Đẩy thêm một lượng luồng (bằng dung lượng nhỏ nhất trên đường đi đó) vào mạng.

3. Điểm múa võ tinh tế (Cạnh ngược / Back edge): Để thuật toán không bị kẹt ở các lựa chọn cục bộ sai lầm, mỗi khi ta đẩy luồng qua cạnh $(u, v)$, đồ thị sẽ tự động sinh ra một cạnh ngược $(v, u)$ với dung lượng tương đương để cho phép "thu hồi" hoặc "điều hướng lại" luồng ở các bước sau nếu cần.

Thuật toán Edmonds-Karp

Ford-Fulkerson gốc có thể chạy vô hạn hoặc rất chậm nếu dung lượng là số thực. Edmonds-Karp giải quyết triệt để vấn đề này bằng cách sử dụng BFS (Breadth-First Search) để tìm đường tăng luồng ngắn nhất (ít cạnh nhất) ở mỗi bước. Nhờ đó, độ phức tạp thời gian được chặn ở mức đa thức cực kỳ ổn định: $O(V \cdot E^2)$.

3. Hiện thực hóa Edmonds-Karp Max Flow bằng Golang

Đoạn code Golang dưới đây cài đặt thuật toán Edmonds-Karp để tính toán lưu lượng cực đại từ nguồn $s$ đến đích $t$:

Go

package main

import (
	"fmt"
	"math"
)

const INF = math.MaxInt32

// BFS tìm đường đi từ s đến t trên đồ thị thặng dư
func bfs(residualGraph [][]int, s, t int, parent []int) bool {
	n := len(residualGraph)
	visited := make([]bool, n)
	queue := []int{s}
	visited[s] = true
	parent[s] = -1

	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]

		for v := 0; v < n; v++ {
			// Nếu chưa thăm và dung lượng thặng dư > 0
			if !visited[v] && residualGraph[u][v] > 0 {
				parent[v] = u
				visited[v] = true
				if v == t {
					return true // Đã tìm thấy đường đến đích
				}
				queue = append(queue, v)
			}
		}
	}
	return false
}

// Tính Max Flow bằng thuật toán Edmonds-Karp
func EdmondsKarp(capacity [][]int, s, t int) int {
	n := len(capacity)
	// Tạo đồ thị thặng dư (Residual Graph), ban đầu giống hệt capacity
	residualGraph := make([][]int, n)
	for i := range capacity {
		residualGraph[i] = make([]int, n)
		copy(residualGraph[i], capacity[i])
	}

	parent := make([]int, n)
	maxFlow := 0

	// Lặp lại việc tìm đường tăng luồng bằng BFS
	for bfs(residualGraph, s, t, parent) {
		// Tìm dung lượng nhỏ nhất dọc theo đường đi vừa tìm được (bottleneck)
		pathFlow := INF
		for v := t; v != s; v = parent[v] {
			u := parent[v]
			if residualGraph[u][v] < pathFlow {
				pathFlow = residualGraph[u][v]
			}
		}

		// Cập nhật dung lượng thặng dư của các cạnh và cạnh ngược trên đường đi
		for v := t; v != s; v = parent[v] {
			u := parent[v]
			residualGraph[u][v] -= pathFlow // Giảm dung lượng chiều đi
			residualGraph[v][u] += pathFlow // Tăng dung lượng cạnh ngược
		}

		maxFlow += pathFlow
	}

	return maxFlow
}

func main() {
	// Số lượng đỉnh trong mạng (từ 0 đến 5)
	// 0: Source (s), 5: Sink (t)
	n := 6
	capacity := make([][]int, n)
	for i := range capacity {
		capacity[i] = make([]int, n)
	}

	// Thiết lập dung lượng các đường ống (cạnh có hướng)
	addEdge := func(u, v, cap int) {
		capacity[u][v] = cap
	}

	addEdge(0, 1, 16)
	addEdge(0, 2, 13)
	addEdge(1, 2, 10)
	addEdge(1, 3, 12)
	addEdge(2, 1, 4)
	addEdge(2, 4, 14)
	addEdge(3, 2, 9)
	addEdge(3, 5, 20)
	addEdge(4, 3, 7)
	addEdge(4, 5, 4)

	source := 0
	sink := 5

	maxFlowValue := EdmondsKarp(capacity, source, sink)
	fmt.Printf("Lưu lượng cực đại (Max Flow) từ nguồn %d đến đích %d là: %d\n", source, sink, maxFlowValue)
}

4. Ứng dụng thực tế trong Hệ thống phân tán

• Tối ưu hóa Băng thông Mạng & CDN: Định tuyến các gói tin truyền tải qua mạng lưới máy chủ phân phối toàn cầu sao cho đạt thông lượng tối đa mà không gây nghẽn mạch tại bất kỳ điểm nút nào.

• Bài toán Ghép cặp cực đại (Maximum Bipartite Matching): Đưa các bài toán phân bổ tài nguyên (như gán công việc cho nhân sự hoặc ghép đơn hàng cho tài xế giao hàng) về dạng mạng luồng để giải quyết trong thời gian đa thức.

Mạng luồng và thuật toán Max Flow là minh chứng tuyệt vời cho việc mô hình hóa các dòng chảy vật lý thành các con số trừu tượng để tối ưu hóa toàn bộ hệ thống lớn.