Dinic Algorithm
Mô tả nguyên lý
Thuật toán tìm luồng cực đại hiệu quả sử dụng đồ thị phân tầng và luồng chặn.
Cài đặt mẫu (Implementation)
// Xây dựng đồ thị tầng qua BFS và tìm luồng chặn qua DFS trên các tầng.
Dinic Algorithm Max Flow
Mô tả nguyên lý
Thuật toán tìm luồng cực đại hiệu quả sử dụng đồ thị phân tầng (level graph) và luồng chặn.
Cài đặt mẫu (Implementation)
// Xây dựng tầng bằng BFS và tìm luồng chặn bằng DFS trên các tầng.
Edmonds-Karp Algorithm
Mô tả nguyên lý
Cải tiến của Ford-Fulkerson bằng cách sử dụng BFS để tìm đường tăng tiến ngắn nhất.
Cài đặt mẫu (Implementation)
// Sử dụng hàng đợi BFS để tìm đường đi ngắn nhất về số cạnh từ nguồn tới đích.
Edmonds-Karp Max Flow
Mô tả nguyên lý
Cải tiến của Ford-Fulkerson bằng cách dùng BFS tìm đường tăng tiến ngắn nhất về số cạnh.
Cài đặt mẫu (Implementation)
// Đảm bảo thời gian chạy đa thức không phụ thuộc vào giá trị luồng lớn.
Ford-Fulkerson (Max Flow)
Mô tả nguyên lý
Thuật toán tìm luồng cực đại trong mạng lưới giao thông dựa trên đường tăng tiến.
Cài đặt mẫu (Implementation)
// Sử dụng DFS tìm đường đi từ nguồn đến đích với dung lượng cạnh dư > 0 và cập nhật luồng.
Ford-Fulkerson Max Flow
Mô tả nguyên lý
Tìm luồng cực đại trong mạng lưới giao thông dựa trên đường tăng tiến.
Cài đặt mẫu (Implementation)
// Sử dụng DFS tìm đường đi từ nguồn đến đích với dung lượng cạnh dư > 0.
Push-Relabel Max Flow Algorithm
Mô tả nguyên lý
Thuật toán đẩy và nhãn lại duy trì luồng quá mức (excess flow) tại các đỉnh trung gian.
Cài đặt mẫu (Implementation)
// Không cần tìm đường đi từ nguồn đến đích liên tục mà xử lý cục bộ từng đỉnh.