了解最大流问题的 python 代码

Question

我正在尝试研究 this 博客 post 中的 google foobar 问题。（问题说明如下。）

作者post在博客中提供了他的代码，并声称由Dinic's algorithm解决了。

我在相关维基百科页面上阅读了 Dinic 的算法并观看了 YouTube video。我发现代码（附在下面）的记录很糟糕，而且我没有找到代码中算法是如何实现的线索。特别是，我没有看到“水平图”和“阻塞流”是在哪里构造的。

谁能看到函数 bfs() 中的大 while 循环在做什么？

给定兔子组的起始房间号，逃生的房间号pods，以及中间每条走廊的每个方向一次可以容纳多少只兔子，计算出如何许多兔子可以在高峰期一次安全地逃生pods。

编写一个函数 answer(entrances, exits, path)，它接受一个整数数组，表示聚集的兔子组的位置，一个整数数组，表示转义 pods 所在的位置，以及一个数组走廊的整数数组，以 int 形式返回每个时间步可以通过的兔子总数。入口和出口是不相交的，因此永远不会重叠。路径元素 path[A][B] = C 描述了从 A 到 B 的走廊在每个时间步可以容纳 C 只兔子。最多有50个房间由走廊相连，一次最多可容纳2000000只兔子。

例如，如果您有：

entrances = [0, 1] 
exits = [4, 5] 
path = [   [0, 0, 4, 6, 0, 0],  # Room 0: Bunnies   
           [0, 0, 5, 2, 0, 0],  # Room 1: Bunnies   
           [0, 0, 0, 0, 4, 4],  # Room 2: Intermediate room   
           [0, 0, 0, 0, 6, 6],  # Room 3: Intermediate room   
           [0, 0, 0, 0, 0, 0],  # Room 4: Escape pods   
           [0, 0, 0, 0, 0, 0],  # Room 5: Escape pods ]

那么在每个时间步，可能会发生以下情况：

0 sends 4/4 bunnies to 2 and 6/6 bunnies to 3 
1 sends 4/5 bunnies to 2 and 2/2 bunnies to 3 
2 sends 4/4 bunnies to 4 and 4/4 bunnies to 5 
3 sends 4/6 bunnies to 4 and 4/6 bunnies to 5

因此，总共有 16 只兔子可以在每个时间步的第 4 步和第 5 步逃脱 pods。（请注意，在此示例中，房间 3 可以将 8 只兔子的任何变体发送到 4 和 5，例如 2/6 和 6/6，但最终答案保持不变。）

def bfs(matrix, source, destination):
    visited = [-1 for i in range(len(matrix))]
    visited[source] = source
    queue = [source]
    while len(queue) > 0:
        top = queue.pop(0)
        for i in range(len(matrix)):
            if (matrix[top][i][1] - matrix[top][i][0]) != 0 and visited[i] == -1:
                if i == destination:
                    # Get route
                    visited[destination] = top
                    path = [destination]
                    temp = destination
                    while temp != source:
                        temp = visited[temp]
                        path.append(temp)
                    path.reverse()
                    # Get flow value and update augmented graph
                    temp = 1
                    total = float("inf")
                    cur = source
                    while temp != len(path):
                        entry = matrix[cur][path[temp]]
                        diff = abs(entry[1]) - entry[0]
                        total = min(total, diff)
                        cur = path[temp]
                        temp += 1
                    temp = 1
                    cur = source
                    while temp != len(path):
                        entry = matrix[cur][path[temp]]
                        if entry[1] < 0: # Already augmented need to flip
                            entry[1] += total
                        else:
                            entry[0] += total
                        entry = matrix[path[temp]][cur]
                        if entry[1] <= 0: # Already augmented need to flip
                            entry[1] -= total
                        else:
                            entry[0] += total
                        cur = path[temp]
                        temp += 1
                    return True
                else:
                    visited[i] = top
                    queue.append(i)
    return False

def answer(entrances, exits, path):
    max_val = sum(list(map(sum, path)))
    aug = []
    for i in range(len(path)):
        aug.append([])
        for j in range(len(path[i])):
            aug[i].append([0, path[i][j]])
        aug[i].append([0, 0])
        if i in exits:
            aug[i].append([0, max_val])
        else:
            aug[i].append([0, 0])
    aug.append([])
    aug.append([])
    for i in range(len(path[0]) + 2):
        if i in entrances:
            aug[-2].append([0, max_val])
        else:
            aug[-2].append([0, 0])
        aug[-1].append([0, 0])
    while bfs(aug, len(aug)-2, len(aug)-1):
        pass
    total = 0
    for i in range(len(aug)):
        total += aug[-2][i][0]
    return total

Answer 1

作者弄错了。这段代码实现了 Edmonds–Karp（专门用于 Ford–Fulkerson，因此 turtle 的评论是正确的），它在残差网络中重复增加最短路径。

了解最大流问题的 python 代码

Understanding a python code for a max flow problem

python

algorithm

graph-theory