用 Python 实现最大流算法：Ford-Fulkerson 和 Edmonds-Karp

2023-04-17 00:00:00 python 算法大流

Ford-Fulkerson算法：

Ford-Fulkerson算法是一种经典的最大流算法，其基本思想是从原图中不断寻找增广路径，直到不存在增广路径为止。

具体实现中，可以使用DFS或BFS遍历增广路径。每次在增广路径上找到最小容量c，然后对该增广路径进行调整：对于每条正向边，流量加上c；对于每条反向边，流量减去c。

这样不断寻找增广路径，直到不存在增广路为止，此时即可得到最大流。

下面是使用DFS实现Ford-Fulkerson算法的Python代码：

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(dict)
        self.V = vertices

    def add_edge(self, u, v, w):
        self.graph[u][v] = w
        self.graph[v][u] = 0

    def dfs(self, s, t, parent):
        visited = [False] * self.V
        stack = []
        stack.append(s)
        visited[s] = True
        parent[s] = -1

        # DFS
        while stack:
            u = stack.pop(-1)
            for v in self.graph[u]:
                if not visited[v] and self.graph[u][v] > 0:
                    stack.append(v)
                    visited[v] = True
                    parent[v] = u

        return True if visited[t] else False

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

        while self.dfs(source, sink, parent):
            path_flow = float("inf")
            s = sink
            while s != source:
                path_flow = min(path_flow, self.graph[parent[s]][s])
                s = parent[s]
            max_flow += path_flow

            v = sink
            while v != source:
                u = parent[v]
                self.graph[u][v] -= path_flow
                self.graph[v][u] += path_flow
                v = parent[v]

        return max_flow

使用样例：

g = Graph(6)
g.add_edge(0, 1, 16)
g.add_edge(0, 2, 13)
g.add_edge(1, 2, 10)
g.add_edge(2, 1, 4)
g.add_edge(1, 3, 12)
g.add_edge(2, 4, 14)
g.add_edge(3, 2, 9)
g.add_edge(3, 5, 20)
g.add_edge(4, 3, 7)
g.add_edge(4, 5, 4)

source = 0
sink = 5
print("Maximum flow: ", g.ford_fulkerson(source, sink))

输出结果：

Maximum flow:  23

Edmonds-Karp算法：

Edmonds-Karp算法是在Ford-Fulkerson算法的基础上进行优化，使用BFS寻找增广路径，使得每次寻找的增广路径都是最短的。

具体实现中，使用BFS遍历增广路径，对于每次遍历到的节点v，记录其通过最短路径到达v的前驱节点u和该路径上的最小残余容量。在遍历完整个增广路径后，可使用该路径上的最小残余容量更新流量，并对该路径上的每条边进行调整。

下面是使用BFS实现Edmonds-Karp算法的Python代码：

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(dict)
        self.V = vertices

    def add_edge(self, u, v, w):
        self.graph[u][v] = w
        self.graph[v][u] = 0

    def bfs(self, s, t, parent):
        visited = [False] * self.V
        queue = []
        queue.append(s)
        visited[s] = True
        parent[s] = -1
        path_flow = float("inf")

        # BFS
        while queue:
            u = queue.pop(0)
            for v in self.graph[u]:
                if not visited[v] and self.graph[u][v] > 0:
                    queue.append(v)
                    visited[v] = True
                    parent[v] = u
                    path_flow = min(path_flow, self.graph[u][v])

        return True if visited[t] else False, path_flow

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

        while True:
            res, path_flow = self.bfs(source, sink, parent)
            if not res:
                break
            max_flow += path_flow

            v = sink
            while v != source:
                u = parent[v]
                self.graph[u][v] -= path_flow
                self.graph[v][u] += path_flow
                v = parent[v]

        return max_flow

使用样例：

g = Graph(6)
g.add_edge(0, 1, 16)
g.add_edge(0, 2, 13)
g.add_edge(1, 2, 10)
g.add_edge(2, 1, 4)
g.add_edge(1, 3, 12)
g.add_edge(2, 4, 14)
g.add_edge(3, 2, 9)
g.add_edge(3, 5, 20)
g.add_edge(4, 3, 7)
g.add_edge(4, 5, 4)

source = 0
sink = 5
print("Maximum flow: ", g.edmonds_karp(source, sink))

输出结果：

Maximum flow:  23

相关文章