Python实现最小费用最大流算法（小白也能看懂的费用流教程）

算法原理简述

常用的求解最小费用最大流的方法是Successive Shortest Path（连续最短路）算法，其核心思想是：

1. 每次在残量网络中寻找一条从源点到汇点的最短费用路径（可用 Bellman-Ford 或 SPFA 实现）；
2. 沿该路径尽可能多地增广流量；
3. 重复上述过程，直到无法再找到增广路径为止。

Python代码实现

下面我们将用 Python 实现一个完整的最小费用最大流算法。我们将使用邻接表存储图，并通过 SPFA（Shortest Path Faster Algorithm）来寻找最短费用路径。

from collections import dequeclass MinCostMaxFlow:    def __init__(self, n):        self.n = n        self.graph = [[] for _ in range(n)]        self.edges = []  # 存储所有边的信息    def add_edge(self, u, v, cap, cost):        """        添加一条从 u 到 v 的边，容量为 cap，单位费用为 cost        同时添加反向边（用于残量网络）        """        forward = [v, len(self.graph[v]), cap, cost]        backward = [u, len(self.graph[u]), 0, -cost]        self.graph[u].append(len(self.edges))        self.edges.append(forward)        self.graph[v].append(len(self.edges))        self.edges.append(backward)    def spfa(self, s, t):        """使用 SPFA 寻找从 s 到 t 的最短费用路径"""        dist = [float('inf')] * self.n        parent = [-1] * self.n        in_queue = [False] * self.n        queue = deque()        dist[s] = 0        queue.append(s)        in_queue[s] = True        while queue:            u = queue.popleft()            in_queue[u] = False            for idx in self.graph[u]:                v, rev_idx, cap, cost = self.edges[idx]                if cap > 0 and dist[u] + cost < dist[v]:                    dist[v] = dist[u] + cost                    parent[v] = idx                    if not in_queue[v]:                        in_queue[v] = True                        queue.append(v)        return dist[t] != float('inf'), dist, parent    def min_cost_max_flow(self, s, t):        """计算从 s 到 t 的最小费用最大流"""        total_flow = 0        total_cost = 0        while True:            found, dist, parent = self.spfa(s, t)            if not found:                break            # 找到路径上的最小剩余容量            flow = float('inf')            cur = t            while cur != s:                edge_idx = parent[cur]                flow = min(flow, self.edges[edge_idx][2])  # cap                cur = self.edges[self.edges[edge_idx][1]][0]  # 回溯到前驱节点            # 更新残量网络            cur = t            while cur != s:                edge_idx = parent[cur]                self.edges[edge_idx][2] -= flow  # 正向边减少容量                rev_idx = self.edges[edge_idx][1]                self.edges[rev_idx][2] += flow   # 反向边增加容量                total_cost += flow * self.edges[edge_idx][3]  # 累加费用                cur = self.edges[rev_idx][0]            total_flow += flow        return total_flow, total_cost

使用示例

假设我们有一个简单的网络：节点 0 是源点，节点 3 是汇点，中间有若干带容量和费用的边。

# 创建一个包含 4 个节点的图mcmf = MinCostMaxFlow(4)# 添加边：(起点, 终点, 容量, 单位费用)mcmf.add_edge(0, 1, 10, 1)mcmf.add_edge(0, 2, 5, 2)mcmf.add_edge(1, 2, 15, 1)mcmf.add_edge(1, 3, 10, 3)mcmf.add_edge(2, 3, 10, 1)# 计算最小费用最大流max_flow, min_cost = mcmf.min_cost_max_flow(0, 3)print(f"最大流量: {max_flow}")print(f"最小费用: {min_cost}")

运行结果可能是：

最大流量: 15最小费用: 35

总结

通过本教程，你已经掌握了如何用 Python 实现最小费用最大流算法。这项技术广泛应用于交通规划、电力网络、任务分配等领域。理解并掌握网络流算法实现，不仅能提升你的算法能力，还能解决许多实际工程问题。

希望这篇关于Python费用流算法的教程对你有帮助！如果你有任何疑问，欢迎在评论区留言交流。