0

我正在尝试为无向图实现 Edmonds–Karp 算法的一个版本。下面的代码有效，但在处理大矩阵时非常慢。

是否可以让 Edmonds–Karp 算法运行得更快，或者我应该继续使用另一种算法，例如“Push Relabel”？我虽然有某种与 bfs 合作的出队，但我不知道该怎么做。

编码：

def bfs(C, F, s, t):
    stack = [s]
    paths={s:[]}
    if s == t:
            return paths[s]
    while(stack):
            u = stack.pop()
            for v in range(len(C)):
                    if(C[u][v]-F[u][v]>0) and v not in paths:
                            paths[v] = paths[u]+[(u,v)]
                            if v == t:
                                    return paths[v]
                            stack.append(v)
    return None

def maxFlow(C, s, t):
    n = len(C) # C is the capacity matrix
    F = [[0] * n for i in range(n)]
    path = bfs(C, F, s, t)
    while path != None:
        flow = min(C[u][v] - F[u][v] for u,v in path)
        for u,v in path:
            F[u][v] += flow
            F[v][u] -= flow
        path = bfs(C,F,s,t)
    return sum(F[s][i] for i in range(n))

C = [[ 0, 3, 3, 0, 0, 0 ],  # s
 [ 3, 0, 2, 3, 0, 0 ],  # o
 [ 0, 2, 0, 0, 2, 0 ],  # p
 [ 0, 0, 0, 0, 4, 2 ],  # q
 [ 0, 0, 0, 2, 0, 2 ],  # r
 [ 0, 0, 0, 0, 2, 0 ]]  # t

source = 0  # A
sink = 5    # F
maxVal = maxFlow(C, source, sink)
print("max_flow_value is: ", maxVal)
4

1 回答 1

1

我认为您的解决方案可以从更好的图形表示中受益。特别要尝试为 BFS 保留邻居列表。实际上，我在这里https://stackoverflow.com/a/23168107/812912关于用于流算法的图形表示写了一个很长的答案

如果您的解决方案仍然太慢，我建议您切换到Dinic 的算法，它在许多任务中对我很有帮助。

于 2021-04-02T12:27:21.690 回答