Thuật toán DSA Edmonds-Karp

Thuật toán Edmonds-Karp

Thuật toán Edmonds-Karp giải bài toán luồng cực đại cho đồ thị có hướng.

Luồng xuất phát từ đỉnh nguồn (\(s\)) và kết thúc ở đỉnh chìm (\(t\)) và mỗi cạnh trong biểu đồ cho phép một luồng, bị giới hạn bởi dung lượng.

Thuật toán Edmonds-Karp rất giống với thuật toán Ford-Fulkerson , ngoại trừ thuật toán Edmonds-Karp sử dụng Tìm kiếm theo chiều rộng (BFS) để tìm các đường dẫn tăng cường nhằm tăng lưu lượng.

Thuật toán Edmonds-Karp hoạt động bằng cách sử dụng Tìm kiếm theo chiều rộng (BFS) để tìm đường dẫn có dung lượng khả dụng từ nguồn đến đích (được gọi là đường dẫn tăng cường ), sau đó gửi càng nhiều luồng càng tốt qua đường dẫn đó.

Thuật toán Edmonds-Karp tiếp tục tìm ra các đường dẫn mới để gửi nhiều luồng hơn cho đến khi đạt được luồng tối đa.

Trong mô phỏng ở trên, thuật toán Edmonds-Karp giải quyết vấn đề luồng tối đa: Nó tìm ra có bao nhiêu luồng có thể được gửi từ đỉnh nguồn \(s\), đến đỉnh đích \(t\) và luồng tối đa đó là số 8.

Các số trong mô phỏng ở trên được viết dưới dạng phân số, trong đó số đầu tiên là luồng và số thứ hai là dung lượng (luồng tối đa có thể có ở cạnh đó). Vì vậy, ví dụ: 0/7 trên cạnh \(s \rightarrow v_2\), nghĩa là có 0 luồng, với dung lượng là 7 trên cạnh đó.

Bạn có thể xem mô tả từng bước cơ bản về cách hoạt động của thuật toán Edmonds-Karp bên dưới, nhưng sau này chúng ta cần đi sâu vào chi tiết hơn để thực sự hiểu nó.

Mạng lưới dư ở Edmonds-Karp

Thuật toán Edmonds-Karp hoạt động bằng cách tạo và sử dụng một thứ gọi là mạng dư , là biểu diễn của biểu đồ gốc.

Trong mạng dư, mọi cạnh đều có dung lượng dư , là dung lượng ban đầu của cạnh, trừ đi luồng trong cạnh đó. Dung lượng dư có thể được coi là dung lượng còn sót lại ở một cạnh có dòng chảy nào đó.

Ví dụ: nếu có luồng 2 ở cạnh \( v_3 \rightarrow v_4 \) và dung lượng là 3 thì luồng dư là 1 ở cạnh đó, vì có chỗ để gửi thêm 1 đơn vị luồng qua cạnh đó bờ rìa.

Các cạnh đảo ngược trong Edmonds-Karp

Thuật toán Edmonds-Karp cũng sử dụng một thứ gọi là các cạnh đảo ngược để gửi luồng ngược lại. Điều này rất hữu ích để tăng tổng lưu lượng.

Để gửi luồng ngược lại, theo hướng ngược lại của cạnh, một cạnh ngược được tạo cho mỗi cạnh ban đầu trong mạng. Thuật toán Edmonds-Karp sau đó có thể sử dụng các cạnh ngược này để gửi luồng theo hướng ngược lại.

Cạnh đảo ngược không có dòng chảy hoặc dung lượng, chỉ có dung lượng dư. Dung lượng dư của cạnh đảo ngược luôn bằng lưu lượng ở cạnh ban đầu tương ứng.

Trong ví dụ của chúng tôi, cạnh \( v_1 \rightarrow v_3 \) có luồng 2, nghĩa là có dung lượng dư là 2 trên cạnh đảo ngược tương ứng \( v_3 \rightarrow v_1 \).

Điều này chỉ có nghĩa là khi có luồng 2 trên cạnh ban đầu \( v_1 \rightarrow v_3 \), thì có khả năng gửi cùng một lượng luồng đó trở lại cạnh đó, nhưng theo hướng ngược lại. Việc sử dụng cạnh đảo ngược để đẩy lùi luồng cũng có thể được coi là hoàn tác một phần của luồng đã được tạo.

Ý tưởng về mạng dư với dung lượng dư trên các cạnh và ý tưởng về các cạnh đảo ngược là trọng tâm trong cách thức hoạt động của thuật toán Edmonds-Karp và chúng tôi sẽ đi sâu vào chi tiết hơn về điều này khi chúng tôi triển khai thuật toán sâu hơn trên trang này.

Chạy qua thủ công

Không có luồng nào trong biểu đồ để bắt đầu.

Thuật toán Edmonds-Karp bắt đầu bằng việc sử dụng Tìm kiếm theo chiều rộng để tìm đường dẫn tăng cường trong đó luồng có thể được tăng lên, đó là \(s \rightarrow v_1 \rightarrow v_3 \rightarrow t\).

Sau khi tìm thấy đường dẫn tăng cường, việc tính toán nút cổ chai được thực hiện để tìm ra lượng luồng có thể được gửi qua đường dẫn đó và luồng đó là: 2.

Vì vậy, một luồng 2 được gửi qua mỗi cạnh trong đường dẫn tăng cường.

Lần lặp tiếp theo của thuật toán Edmonds-Karp là thực hiện lại các bước sau: Tìm một đường dẫn tăng cường mới, tìm xem luồng trong đường dẫn đó có thể tăng lên bao nhiêu và tăng luồng dọc theo các cạnh trong đường dẫn đó cho phù hợp.

Đường dẫn mở rộng tiếp theo được tìm thấy là \(s \rightarrow v_1 \rightarrow v_4 \rightarrow t \).

Luồng chỉ có thể tăng thêm 1 trong đường dẫn này vì chỉ còn chỗ cho một đơn vị luồng nữa ở cạnh \( s \rightarrow v_1 \).

Đường dẫn mở rộng tiếp theo được tìm thấy là \(s \rightarrow v_2 \rightarrow v_4 \rightarrow t\).

Lưu lượng có thể tăng lên 3 trong đường dẫn này. Nút cổ chai (cạnh giới hạn) là \( v_2 \rightarrow v_4 \) vì dung lượng là 3.

Đường dẫn tăng cường cuối cùng được tìm thấy là \(s \rightarrow v_2 \rightarrow v_1 \rightarrow v_4 \rightarrow t\).

Luồng chỉ có thể tăng thêm 2 trong đường dẫn này do cạnh \( v_4 \rightarrow t \) là nút thắt cổ chai trong đường dẫn này chỉ có không gian cho thêm 2 đơn vị luồng (\(capacity-flow=1\)).

Tại thời điểm này, không thể tìm thấy đường dẫn tăng cường mới (không thể tìm thấy đường dẫn có thể gửi nhiều luồng hơn từ \(s\) đến \(t\)), có nghĩa là luồng tối đa đã được tìm thấy, và thuật toán Edmonds-Karp đã hoàn thành.

Luồng tối đa là 8. Như bạn có thể thấy trong hình trên, luồng (8) đi ra khỏi đỉnh nguồn \(s\), giống như luồng đi vào đỉnh đích \(t\).

Ngoài ra, nếu bạn lấy bất kỳ đỉnh nào khác ngoài \(s\) hoặc \(t\), bạn có thể thấy rằng lượng dòng chảy đi vào một đỉnh cũng giống như lượng dòng chảy đi ra khỏi đỉnh đó. Đây là cái mà chúng ta gọi là bảo toàn luồng và điều này phải đúng cho tất cả các mạng luồng như vậy (đồ thị có hướng trong đó mỗi cạnh có một luồng và dung lượng).

Triển khai thuật toán Edmonds-Karp

Để triển khai thuật toán Edmonds-Karp, chúng tôi tạo một lớp Graph .

Graph biểu thị đồ thị với các đỉnh và cạnh của nó:

 class Graph:
    def __init__(self, size):
        self.adj_matrix = [[0] * size for _ in range(size)]
        self.size = size
        self.vertex_data = [''] * size

    def add_edge(self, u, v, c):
        self.adj_matrix[u][v] = c

    def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

Dòng 3: Chúng ta tạo adj_matrix để chứa tất cả các cạnh và dung lượng của cạnh. Giá trị ban đầu được đặt thành 0 .

Dòng 4: size là số đỉnh của đồ thị.

Dòng 5: vertex_data chứa tên của tất cả các đỉnh.

Dòng 7-8: Phương thức add_edge được sử dụng để thêm một cạnh từ đỉnh u đến đỉnh v , với dung lượng c .

Dòng 10-12: Phương thức add_vertex_data được sử dụng để thêm tên đỉnh vào biểu đồ. Chỉ mục của đỉnh được đưa ra cùng với đối vertex và data là tên của đỉnh.

Lớp Graph cũng chứa phương thức bfs để tìm các đường dẫn mở rộng, sử dụng Breadth-First-Search:

    def bfs(self, s, t, parent):
        visited = [False] * self.size
        queue = []  # Using list as a queue
        queue.append(s)
        visited[s] = True

        while queue:
            u = queue.pop(0)  # Pop from the start of the list

            for ind, val in enumerate(self.adj_matrix[u]):
                if not visited[ind] and val > 0:
                    queue.append(ind)
                    visited[ind] = True
                    parent[ind] = u

        return visited[t]

Dòng 15-18: Mảng visited giúp tránh việc xem lại các đỉnh giống nhau trong quá trình tìm kiếm đường dẫn tăng cường. queue chứa các đỉnh cần khám phá, quá trình tìm kiếm luôn bắt đầu từ đỉnh nguồn s .

Dòng 20-21: Miễn là có các đỉnh cần khám phá trong queue , hãy lấy đỉnh đầu tiên ra khỏi hàng queue để có thể tìm thấy đường dẫn từ đó đến đỉnh tiếp theo.

Dòng 23: Đối với mọi đỉnh liền kề với đỉnh hiện tại.

Dòng 24-27: Nếu đỉnh liền kề chưa được thăm và còn dư dung lượng trên cạnh của đỉnh đó: thêm nó vào hàng các đỉnh cần khám phá, đánh dấu nó là đã thăm và đặt parent của đỉnh liền kề là đỉnh hiện tại u .

Mảng parent giữ đỉnh cha của một đỉnh, tạo một đường dẫn từ đỉnh chìm, quay trở lại đỉnh nguồn. parent này được sử dụng trong thuật toán Edmonds-Karp, ngoài phương pháp bfs , để tăng luồng trong đường dẫn tăng cường.

Dòng 29: Dòng cuối cùng trả visited[t] , điều này true nếu đường dẫn tăng cường kết thúc ở nút chìm t . Trả về true có nghĩa là đường dẫn tăng cường đã được tìm thấy.

Phương thức edmonds_karp là phương thức cuối cùng chúng ta thêm vào lớp Graph :

    def edmonds_karp(self, source, sink):
        parent = [-1] * self.size
        max_flow = 0

        while self.bfs(source, sink, parent):
            path_flow = float("Inf")
            s = sink
            while(s != source):
                path_flow = min(path_flow, self.adj_matrix[parent[s]][s])
                s = parent[s]

            max_flow += path_flow
            v = sink
            while(v != source):
                u = parent[v]
                self.adj_matrix[u][v] -= path_flow
                self.adj_matrix[v][u] += path_flow
                v = parent[v]

            path = []
            v = sink
            while(v != source):
                path.append(v)
                v = parent[v]
            path.append(source)
            path.reverse()
            path_names = [self.vertex_data[node] for node in path]
            print("Path:", " -> ".join(path_names), ", Flow:", path_flow)

        return max_flow

Ban đầu, mảng parent chứa các giá trị chỉ mục không hợp lệ, vì không có đường dẫn tăng cường nào để bắt đầu và max_flow là 0 , đồng thời vòng lặp while tiếp tục tăng max_flow miễn là có đường dẫn tăng cường để tăng lưu lượng vào.

Dòng 35: Vòng lặp while bên ngoài đảm bảo thuật toán Edmonds-Karp tiếp tục tăng luồng miễn là có các đường dẫn tăng cường để tăng luồng dọc theo.

Dòng 36-37: Luồng ban đầu dọc theo đường dẫn tăng cường là vô hạn và mức tăng luồng có thể có sẽ được tính bắt đầu từ đỉnh chìm.

Dòng 38-40: Giá trị của path_flow được tìm thấy bằng cách đi lùi từ đỉnh chìm về phía đỉnh nguồn. Giá trị thấp nhất của dung lượng dư dọc theo đường dẫn là giá trị quyết định lượng luồng có thể được gửi trên đường dẫn.

Dòng 42: path_flow được tăng thêm path_flow .

Dòng 44-48: Bước qua đường dẫn tăng cường, đi ngược từ sink đến nguồn, dung lượng dư giảm với path_flow ở các cạnh phía trước và dung lượng dư tăng lên với path_flow ở các cạnh đảo ngược.

Dòng 50-58: Phần mã này chỉ để in để chúng tôi có thể theo dõi mỗi khi tìm thấy đường dẫn tăng cường và lượng luồng được gửi qua đường dẫn đó.

Sau khi xác định lớp Graph , các đỉnh và cạnh phải được xác định để khởi tạo biểu đồ cụ thể và mã hoàn chỉnh cho ví dụ về thuật toán Edmonds-Karp trông như thế này:

 class Graph:
    def __init__(self, size):
        self.adj_matrix = [[0] * size for _ in range(size)]
        self.size = size
        self.vertex_data = [''] * size

    def add_edge(self, u, v, c):
        self.adj_matrix[u][v] = c

    def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

    def bfs(self, s, t, parent):
        visited = [False] * self.size
        queue = []  # Using list as a queue
        queue.append(s)
        visited[s] = True

        while queue:
            u = queue.pop(0)  # Pop from the start of the list

            for ind, val in enumerate(self.adj_matrix[u]):
                if not visited[ind] and val > 0:
                    queue.append(ind)
                    visited[ind] = True
                    parent[ind] = u

        return visited[t]

    def edmonds_karp(self, source, sink):
        parent = [-1] * self.size
        max_flow = 0

        while self.bfs(source, sink, parent):
            path_flow = float("Inf")
            s = sink
            while(s != source):
                path_flow = min(path_flow, self.adj_matrix[parent[s]][s])
                s = parent[s]

            max_flow += path_flow
            v = sink
            while(v != source):
                u = parent[v]
                self.adj_matrix[u][v] -= path_flow
                self.adj_matrix[v][u] += path_flow
                v = parent[v]

            path = []
            v = sink
            while(v != source):
                path.append(v)
                v = parent[v]
            path.append(source)
            path.reverse()
            path_names = [self.vertex_data[node] for node in path]
            print("Path:", " -> ".join(path_names), ", Flow:", path_flow)

        return max_flow

# Example usage:
g = Graph(6)
vertex_names = ['s', 'v1', 'v2', 'v3', 'v4', 't']
for i, name in enumerate(vertex_names):
    g.add_vertex_data(i, name)

g.add_edge(0, 1, 3)  # s  -> v1, cap: 3
g.add_edge(0, 2, 7)  # s  -> v2, cap: 7
g.add_edge(1, 3, 3)  # v1 -> v3, cap: 3
g.add_edge(1, 4, 4)  # v1 -> v4, cap: 4
g.add_edge(2, 1, 5)  # v2 -> v1, cap: 5
g.add_edge(2, 4, 3)  # v2 -> v4, cap: 3
g.add_edge(3, 4, 3)  # v3 -> v4, cap: 3
g.add_edge(3, 5, 2)  # v3 -> t,  cap: 2
g.add_edge(4, 5, 6)  # v4 -> t,  cap: 6

source = 0; sink = 5
print("The maximum possible flow is %d " % g.edmonds_karp(source, sink))

Độ phức tạp về thời gian của Thuật toán Edmonds-Karp

Sự khác biệt giữa Edmonds-Karp và Ford-Fulkerson là Edmonds-Karp sử dụng Tìm kiếm theo chiều rộng (BFS) để tìm các đường dẫn mở rộng, trong khi Ford-Fulkerson sử dụng Tìm kiếm theo chiều sâu (DFS).

Điều này có nghĩa là thời gian chạy Edmonds-Karp dễ dự đoán hơn Ford-Fulkerson, vì Edmonds-Karp không bị ảnh hưởng bởi giá trị luồng tối đa.

Với số đỉnh \(V\), số cạnh \(E\), độ phức tạp về thời gian của thuật toán Edmonds-Karp là

\[ O(V \cdot E^2) \]

Điều này có nghĩa là Edmonds-Karp không phụ thuộc vào luồng cực đại, giống như Ford-Fulkerson, mà phụ thuộc vào số đỉnh và cạnh mà chúng ta có.

Lý do chúng tôi nhận được độ phức tạp về thời gian này đối với Edmonds-Karp là vì nó chạy BFS có độ phức tạp về thời gian \(O(E+V)\).

Nhưng nếu chúng ta giả sử một trường hợp xấu cho Edmonds-Karp, với đồ thị dày đặc, trong đó số cạnh \(E\) lớn hơn nhiều so với số đỉnh \(V\), thì độ phức tạp về thời gian của BFS sẽ trở thành \(O (E)\).

BFS phải chạy một lần cho mỗi đường dẫn tăng cường và thực tế có thể tìm thấy các đường dẫn tăng cường gần \(V \cdot E \) trong quá trình chạy thuật toán Edmonds-Karp.

Vì vậy, BFS với độ phức tạp về thời gian \(O(E)\) có thể chạy gần với \(V \cdot E \) lần trong trường hợp xấu nhất, điều đó có nghĩa là chúng ta có tổng độ phức tạp về thời gian cho Edmonds-Karp: \( O(V \cdot E \cdot E) = O(V \cdot E^2) \).