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

Thuật toán Ford-Fulkerson là một trong những thuật toán được sử dụng phổ biến nhất trong lĩnh vực tối ưu hóa mạng, đặc biệt là trong giải quyết các bài toán về luồng cực đại trong một mạng lưới. Để hiểu rõ hơn về cách cài đặt thuật toán này trong lập trình, chúng ta cần đi qua từng bước cụ thể của thuật toán và triển khai nó bằng một ngôn ngữ lập trình như Python.

Nguyên lý của Thuật toán Ford-Fulkerson

Thuật toán Ford-Fulkerson hoạt động trên cơ sở tìm kiếm các đường đi tăng (augmenting path) trong một mạng lưới có trọng số từ nguồn (source) đến đích (sink). Đường đi tăng là một đường mà theo đó có thể tăng luồng bằng cách giảm phần còn lại (residual capacity).

Mỗi khi tìm được một đường đi tăng, thuật toán sẽ tăng luồng theo đường đi này và cập nhật mạng lưới cho đến khi không còn đường đi tăng nào nữa.

Các bước triển khai Thuật toán Ford-Fulkerson

1. Khởi tạo Luồng: Bắt đầu với luồng bằng 0.
2. Tìm Đường đi Tăng Bằng BFS hoặc DFS: Sử dụng thuật toán tìm kiếm chiều rộng (BFS) hoặc tìm kiếm chiều sâu (DFS) để tìm các đường đi tăng từ nguồn tới đích.
3. Cập nhật Mạng Lưới: Sau khi tìm được đường đi tăng, cập nhật các cạnh của mạng lưới, tức là giảm trọng số của cạnh và tăng trọng số của cạnh ngược lại.
4. Lặp Lại: Tiếp tục lặp lại việc tìm kiếm đường đi tăng cho đến khi không còn đường đi tăng nào tồn tại.

Cài đặt Chi tiết bằng Python

from collections import deque

# Hàm BFS để tìm đường đi tăng trong mạng lưới
def bfs(residual_graph, source, sink, parent):
    visited = [False] * len(residual_graph)
    queue = deque([source])
    visited[source] = True

    while queue:
        u = queue.popleft()
        for ind, val in enumerate(residual_graph[u]):
            if not visited[ind] and val > 0:
                queue.append(ind)
                visited[ind] = True
                parent[ind] = u
                if ind == sink:
                    return True
    return False

# Hàm chính của Thuật toán Ford-Fulkerson
def ford_fulkerson(graph, source, sink):
    residual_graph = [row[:] for row in graph]  # Sao chép đồ thị để tạo đồ thị dư
    parent = [-1] * len(graph)
    max_flow = 0

    # Lặp lại cho đến khi không còn đường đi tăng
    while bfs(residual_graph, source, sink, parent):
        path_flow = float('Inf')
        s = sink

        # Tìm luồng cực đại có thể đi qua đường đi tăng này
        while s != source:
            path_flow = min(path_flow, residual_graph[parent[s]][s])
            s = parent[s]

        # Cập nhật đồ thị dư bằng cách giảm luồng theo đường đi tăng này
        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

# Đồ thị nhập vào dạng ma trận trọng số (graph)
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  # Đỉnh nguồn
sink = 5    # Đỉnh đích

print(f'Giá trị của luồng cực đại là: {ford_fulkerson(graph, source, sink)}')

Giải thích Code

1. bfs: Hàm này tìm kiếm một đường đi tăng từ nguồn đến đích trong đồ thị dư. Nó sử dụng hàng đợi để thực hiện tìm kiếm theo chiều rộng.
2. ford_fulkerson: Hàm chính của thuật toán, nơi luồng cực đại được tính toán. Hàm này lặp lại việc tìm kiếm và cập nhật đường đi tăng cho đến khi không còn đường tăng nào nữa.
3. graph: Đầu vào của đồ thị dưới dạng ma trận trọng số. Giá trị tại vị trí [i][j] là trọng số của cạnh từ đỉnh i đến đỉnh j.

Cài đặt trên không chỉ giúp hiểu rõ hơn về thuật toán mà còn cung cấp mẫu cụ thể để áp dụng vào các bài toán luồng trong mạng lưới. Quan trọng là giữ cho đồ thị dư đúng đắn và đảm bảo rằng thuật toán sẽ dừng khi không còn đường đi tăng nào nữa.