网络流问题 | 最大流

💧Network Flow | Maximum Flow Problem

前言

在最大流问题中，给定一个有向图，其中每条边都有一个容量限制，同时有一个源点和一个汇点。最大流问题的目标是找到从源点到汇点的最大流量，即通过网络中的路径，使得从源点到汇点的流量最大化。

增广路是一条路径，它满足以下两个条件：

  1. 路径上的边的剩余容量大于0。
  2. 路径上的边的剩余容量的最小值称为该路径的容量。

基本步骤

  • 初始化流量为0
  • 在图中寻找一条增广路
  • 如果找到增广路，将流量沿着增广路增加到容量限制
  • 重复步骤2和步骤3，直到无法找到增广路为止
  • 最终的流量即为最大流。

但是这个算法太粗糙了，很容易举出例子，流量用尽了可是最后得到的并非是最大流量，结果和前面选择的路径有关系

所以需要引入一种”撤销“思想，允许犯错

Ford-Fulkerson算法

  • 两个图
    • 最大流量图和剩余流量图
  • 反向边
    • 这个算法最关键的部分 就是这条边减少多少流量 同时添加一个相应流量的反向边

可以理解为 你现在占用了该路径这么多流量 但是有机会抵消这个操作 来探索更大流的方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
from collections import defaultdict

class Graph:
    def __init__(self, graph):
        self.graph = graph
        self.ROW = len(graph)
  
    # 使用深度优先搜索查找增广路径
    def BFS(self, s, t, parent):
        visited = [False] * (self.ROW)
        queue = []
        queue.append(s)
        visited[s] = True
        
        while queue:
            u = queue.pop(0)
  
            for ind, val in enumerate(self.graph[u]):
                if visited[ind] == False and val > 0:
                    queue.append(ind)
                    visited[ind] = True
                    parent[ind] = u
                    if ind == t:
                        return True
  
        return False
  
    # Ford-Fulkerson算法求解最大流
    def FordFulkerson(self, source, sink):
        parent = [-1] * (self.ROW)
        max_flow = 0
        while self.BFS(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

# 测试代码
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]]

g = Graph(graph)
source = 0
sink = 5
max_flow = g.FordFulkerson(source, sink)
print("最大流量为:", max_flow)