Cấu trúc dữ liệu và Giải thuật Bài 118: Luồng cực tiểu chi phí (Min-Cost Max-Flow - MCMF & Thuật toán SPFA) - Tối ưu hóa bài toán phân bổ vận tải có ràng buộc ngân sách.

Ở Bài 111, thuật toán Luồng cực đại (Max Flow) giải quyết bài toán đẩy lưu lượng lớn nhất từ nguồn $s$ đến đích $t$ mà chỉ quan tâm đến dung lượng (Capacity). Tuy nhiên, trong các bài toán vận hành logistics, hạ tầng mạng viễn thông, hay cân bằng tải dịch vụ đám mây, mỗi tuyến đường ống không chỉ có giới hạn thể tích mà còn đi kèm một đơn giá chi phí (Unit Cost).

Ví dụ: Bạn cần vận chuyển $10,000$ tấn hàng hóa từ các kho tổng đến hệ thống siêu thị. Có nhiều lộ trình trung chuyển với cước phí và giới hạn trọng tải khác nhau. Làm thế nào để đẩy đủ số lượng hàng hóa tối đa đến đích nhưng với tổng chi phí tài chính thấp nhất? Đó chính là bài toán Luồng cực tiểu chi phí (Minimum-Cost Maximum-Flow - MCMF).

1. Mô hình toán học của mạng luồng có chi phí

Mạng luồng được mở rộng thành đồ thị có hướng $G = (V, E)$ , trong đó mỗi cạnh $(u, v)$ có hai tham số:

Dung lượng (Capacity - $c(u, v)$ ): Lưu lượng tối đa cho phép chạy qua cạnh.
Đơn giá chi phí (Unit Cost - $w(u, v)$ ): Chi phí phát sinh khi gửi một đơn vị luồng qua cạnh.

Mục tiêu của bài toán MCMF là tìm một hàm luồng $f(u, v)$ sao cho:

Tổng luồng đi từ $s$ đến $t$ đạt cực đại (Max Flow).
Tổng chi phí vận hành đạt cực tiểu:

$\text{Total Cost} = \sum_{(u, v) \in E} f(u, v) \cdot w(u, v) \to \min$

2. Bản chất đồ thị thặng dư và Cạnh có trọng số âm

Tương tự thuật toán Ford-Fulkerson, MCMF duy trì đồ thị thặng dư (Residual Graph) để cho phép "hủy bỏ" hoặc "điều hướng lại" luồng:

Cạnh xuôi $(u, v)$ : Dung lượng còn lại $c_f(u, v) = c(u, v) - f(u, v)$ , chi phí là $+w(u, v)$ .
Cạnh ngược $(v, u)$ : Dung lượng còn lại $c_f(v, u) = f(u, v)$ , chi phí là $-w(u, v)$ .

Chi phí âm trên cạnh ngược xuất hiện vì việc đẩy luồng ngược qua cạnh $(v, u)$ tương đương với việc hủy bỏ một phần luồng đã đẩy trước đó qua $(u, v)$ , giúp hệ thống thu hồi lại số tiền chi phí đã tính.

Do đồ thị thặng dư xuất hiện các cạnh có trọng số âm, thuật toán tìm đường đi ngắn nhất Dijkstra thông thường không thể áp dụng trực tiếp. Để tìm đường tăng luồng có chi phí nhỏ nhất, chúng ta sử dụng Thuật toán SPFA (Shortest Path Faster Algorithm) — phiên bản tối ưu hóa bằng hàng đợi (Queue-based) của thuật toán Bellman-Ford.

3. Thuật toán Successive Shortest Path (SSP) kết hợp SPFA

Thuật toán thực hiện lặp qua các bước:

Tìm đường tăng luồng ngắn nhất: Dùng SPFA trên đồ thị thặng dư để tìm đường đi từ nguồn $s$ đến đích $t$ có tổng chi phí nhỏ nhất (dựa trên trọng số $w$ ).
Dừng vòng lặp: Nếu SPFA không tìm thấy đường đi nào từ $s$ đến $t$ có dung lượng thặng dư $> 0$ , mạng đã đạt trạng thái luồng cực đại.
Tăng luồng: Xác định dung lượng nghẽn (bottleneck capacity $\Delta$ ) dọc theo đường đi vừa tìm được.
Cập nhật thặng dư và chi phí:
- Tăng luồng của cạnh xuôi và giảm dung lượng thặng dư đi $\Delta$ .
- Tăng dung lượng thặng dư của cạnh ngược thêm $\Delta$ .
- Cộng thêm $\Delta \times \text{độ dài đường đi ngắn nhất}$ vào tổng chi phí.

4. Hiện thực hóa Min-Cost Max-Flow bằng Golang

Đoạn mã Golang dưới đây cài đặt MCMF sử dụng SPFA với cấu trúc đồ thị thặng dư lưu cạnh đối ngẫu (rev):

package main

import (
	"fmt"
	"math"
)

const INF = math.MaxInt32

// Edge biểu diễn một cạnh trong đồ thị thặng dư
type Edge struct {
	to       int // Đỉnh đích
	capacity int // Dung lượng thặng dư còn lại
	cost     int // Đơn giá chi phí trên mỗi đơn vị luồng
	rev      int // Chỉ số của cạnh ngược trong danh sách kề của đỉnh 'to'
}

type MCMF struct {
	n   int
	adj [][]Edge
}

func NewMCMF(n int) *MCMF {
	return &MCMF{
		n:   n,
		adj: make([][]Edge, n),
	}
}

// AddEdge thêm một cạnh có hướng từ u sang v với dung lượng cap và chi phí cost
func (m *MCMF) AddEdge(u, v, cap, cost int) {
	// Cạnh xuôi: dung lượng cap, chi phí cost
	forward := Edge{to: v, capacity: cap, cost: cost, rev: len(m.adj[v])}
	// Cạnh ngược: dung lượng 0, chi phí -cost
	backward := Edge{to: u, capacity: 0, cost: -cost, rev: len(m.adj[u])}

	m.adj[u] = append(m.adj[u], forward)
	m.adj[v] = append(m.adj[v], backward)
}

// SPFA tìm đường đi có tổng chi phí nhỏ nhất từ s đến t trên đồ thị thặng dư
func (m *MCMF) spfa(s, t int, dist, prevNode, prevEdge []int) bool {
	for i := 0; i < m.n; i++ {
		dist[i] = INF
	}
	inQueue := make([]bool, m.n)
	queue := []int{s}

	dist[s] = 0
	inQueue[s] = true

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

		for i, e := range m.adj[u] {
			// Chỉ xét cạnh có dung lượng thặng dư > 0
			if e.capacity > 0 && dist[u]+e.cost < dist[e.to] {
				dist[e.to] = dist[u] + e.cost
				prevNode[e.to] = u
				prevEdge[e.to] = i

				if !inQueue[e.to] {
					queue = append(queue, e.to)
					inQueue[e.to] = true
				}
			}
		}
	}

	return dist[t] != INF
}

// ComputeMCMF tính toán luồng cực đại và chi phí cực tiểu tương ứng
func (m *MCMF) ComputeMCMF(s, t int) (maxFlow int, minCost int) {
	dist := make([]int, m.n)
	prevNode := make([]int, m.n)
	prevEdge := make([]int, m.n)

	for m.spfa(s, t, dist, prevNode, prevEdge) {
		// 1. Tìm bottleneck capacity trên đường đi ngắn nhất
		push := INF
		for curr := t; curr != s; curr = prevNode[curr] {
			p := prevNode[curr]
			idx := prevEdge[curr]
			if m.adj[p][idx].capacity < push {
				push = m.adj[p][idx].capacity
			}
		}

		// 2. Cập nhật dung lượng thặng dư của các cạnh và cạnh ngược
		for curr := t; curr != s; curr = prevNode[curr] {
			p := prevNode[curr]
			idx := prevEdge[curr]
			revIdx := m.adj[p][idx].rev

			m.adj[p][idx].capacity -= push
			m.adj[curr][revIdx].capacity += push
		}

		// 3. Tích lũy kết quả
		maxFlow += push
		minCost += push * dist[t]
	}

	return maxFlow, minCost
}

func main() {
	// Hệ thống vận tải gồm 4 nút:
	// 0: Trung tâm phân phối (Source)
	// 1: Trạm trung chuyển A
	// 2: Trạm trung chuyển B
	// 3: Điểm nhận hàng (Sink)
	n := 4
	mcmf := NewMCMF(n)

	// AddEdge(u, v, capacity, unit_cost)
	mcmf.AddEdge(0, 1, 3, 1)  // Đi qua trạm A rẻ (cost=1) nhưng dung lượng tối đa 3
	mcmf.AddEdge(0, 2, 2, 5)  // Đi qua trạm B đắt (cost=5), dung lượng tối đa 2
	mcmf.AddEdge(1, 2, 1, 2)  // Nối giữa A và B
	mcmf.AddEdge(1, 3, 2, 7)  // Từ A đến đích: cost=7, cap=2
	mcmf.AddEdge(2, 3, 4, 2)  // Từ B đến đích: cost=2, cap=4

	source := 0
	sink := 3

	flow, cost := mcmf.ComputeMCMF(source, sink)
	fmt.Printf("Luồng cực đại đạt được: %d đơn vị\n", flow)
	fmt.Printf("Tổng chi phí tối thiểu để vận chuyển lượng hàng trên: %d USD\n", cost)
}

5. Ứng dụng thực tế

Bài toán phân bổ công việc có trọng số (Weighted Bipartite Matching): Thay vì dùng thuật toán Hungary (Hungarian algorithm) $O(N^3)$ , ta có thể chuyển bài toán gán người cho việc kèm chi phí/lương thưởng thành một mạng luồng MCMF giải quyết nhanh gọn.
Định tuyến mạng phân phối nội dung (CDN Traffic Steering): Định tuyến lưu lượng người dùng tải video đến các cụm máy chủ biên (Edge Points of Presence) sao cho vừa thỏa mãn hạn mức băng thông từng ISP, vừa tối thiểu hóa chi phí trung chuyển băng thông (Transit Cost).
Mạng lưới vận tải hàng không (Airline Crew Scheduling): Xếp lịch bay cho các phi hành đoàn qua các chặng trung chuyển với mục tiêu giảm thiểu chi phí ăn ở, phụ cấp qua đêm mà vẫn bảo đảm đầy đủ nhân sự cho mọi chuyến bay.

cấu trúc dữ liệu

1. Mô hình toán học của mạng luồng có chi phí

2. Bản chất đồ thị thặng dư và Cạnh có trọng số âm

3. Thuật toán Successive Shortest Path (SSP) kết hợp SPFA

4. Hiện thực hóa Min-Cost Max-Flow bằng Golang

5. Ứng dụng thực tế

Mục lục