Mạng và Luồng

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 7)

Mạng và Luồng

Dinic Algorithm

Thời gian (Time) O(V^2 * E)
Không gian (Space) O(V + E)

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.
Mạng và Luồng

Dinic Algorithm Max Flow

Thời gian (Time) O(V^2 * E)
Không gian (Space) O(V + E)

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.
Mạng và Luồng

Edmonds-Karp Algorithm

Thời gian (Time) O(V * E^2)
Không gian (Space) O(V + E)

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.
Mạng và Luồng

Edmonds-Karp Max Flow

Thời gian (Time) O(V * E^2)
Không gian (Space) O(V + E)

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.
Mạng và Luồng

Ford-Fulkerson (Max Flow)

Thời gian (Time) O(E * max_flow)
Không gian (Space) O(V)

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.
Mạng và Luồng

Ford-Fulkerson Max Flow

Thời gian (Time) O(E * max_flow)
Không gian (Space) O(V)

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.
Mạng và Luồng

Push-Relabel Max Flow Algorithm

Thời gian (Time) O(V^2 * E)
Không gian (Space) O(V + E)

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.