Cài đặt thuật toán Edmonds-Karp trong lập trình

Thuật toán Edmonds-Karp là một biến thể của thuật toán Ford-Fulkerson dùng để tìm luồng cực đại trong mạng lưới. Nó được áp dụng rộng rãi trong các bài toán tối ưu hóa mạng, như luồng cực đại trong đồ thị, cắt nhỏ nhất, cũng như trong các lĩnh vực vận tải và xử lý dữ liệu.

Khái niệm cơ bản

Trước khi khám phá chi tiết cách cài đặt, ta cần nắm vững một số khái niệm sau:

• Luồng cực đại: Đây là thuật ngữ chỉ lượng luồng lớn nhất mà ta có thể truyền từ điểm nguồn (source) tới điểm đích (sink) trong một mạng lưới.
• Đường tăng luồng (Augmenting Path): Đây là một đường đi từ nguồn tới đích mà ta có thể tăng luồng thông qua nó.
• Đồ thị thặng dư (Residual Graph): Đồ thị này biểu thị khả năng tăng luồng qua các cạnh sau khi đã có một luồng ban đầu đi qua.

Nguyên lý hoạt động

Thuật toán Edmonds-Karp sử dụng thuật toán duyệt theo chiều rộng (BFS) để tìm đường ngắn nhất từ nguồn tới đích trong đồ thị thặng dư. Quy trình này được lặp đi lặp lại cho đến khi không còn đường tăng luồng nào.

Cài đặt thuật toán

Dưới đây là cách cài đặt thuật toán bằng ngôn ngữ lập trình Python:

from collections import deque

# Hàm BFS tìm đường từ nguồn đến đích trong đồ thị thặng dư
def bfs(residual_graph, source, sink, parent):
    visited = [False] * len(residual_graph)
    queue = deque([source])
    visited[source] = True

    while queue:
        u = queue.popleft()
        
        for v, capacity in enumerate(residual_graph[u]):
            if not visited[v] and capacity > 0:  # Thăm đỉnh nếu chưa thăm và còn dung lượng
                queue.append(v)
                visited[v] = True
                parent[v] = u
                if v == sink:
                    return True
    return False

# Hàm chính của thuật toán Edmonds-Karp
def edmonds_karp(graph, source, sink):
    residual_graph = [row[:] for row in graph]  # Tạo đồ thị thặng dư
    parent = [-1] * len(graph)  # Lưu vết đường đi
    max_flow = 0

    while bfs(residual_graph, source, sink, parent):
        path_flow = float('Inf')
        s = sink

        # Tìm khả năng tăng luồng tối đa trên đường tìm được
        while s != source:
            path_flow = min(path_flow, residual_graph[parent[s]][s])
            s = parent[s]

        # Cập nhật dung lượng trên đường đi
        v = sink
        while v != source:
            u = parent[v]
            residual_graph[u][v] -= path_flow
            residual_graph[v][u] += path_flow
            v = parent[v]

        max_flow += path_flow

    return max_flow

# Ví dụ sử dụng
graph = [
    [0, 16, 13, 0, 0, 0],
    [0, 0, 10, 12, 0, 0],
    [0, 4, 0, 0, 14, 0],
    [0, 0, 9, 0, 0, 20],
    [0, 0, 0, 7, 0, 4],
    [0, 0, 0, 0, 0, 0]
]
source = 0
sink = 5

print("Giá trị luồng cực đại là:", edmonds_karp(graph, source, sink))

Giải thích

1. Hàm BFS:

   • Khởi tạo hàng đợi và danh sách visited.
   • Duyệt qua các đỉnh, thêm các đỉnh kế tiếp có khả năng tăng luồng vào hàng đợi.
   • Trả về True nếu có thể tìm thấy đường tăng luồng.

2. Hàm Edmonds-Karp chính:

   • Tạo bản sao của đồ thị gốc để làm đồ thị thặng dư.
   • Sử dụng BFS để tìm đường tăng luồng.
   • Tính toán khả năng tăng luồng tối đa path_flow trên đường tìm được.
   • Cập nhật đồ thị thặng dư và tăng giá trị luồng cực đại dựa trên path_flow.

Kết luận

Thuật toán Edmonds-Karp là một trong các phương pháp hiệu quả để giải bài toán luồng cực đại, sử dụng BFS để đảm bảo tìm được đường ngắn nhất ở mỗi bước, từ đó tối ưu thời gian tìm kiếm đường tăng luồng với độ phức tạp thời gian là O(VE^2). Cài đặt trên không chỉ giải thích cơ bản mà còn cung cấp mã nguồn tham khảo giúp bạn có thể triển khai thuật toán trong các hệ thống thực tế.