Edmonds–Karp 时间复杂度

Question

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

是否可以让 Edmonds–Karp 算法更快运行，或者我应该继续使用其他算法，例如“Push Relabel”？我有一些与 bfs 一起工作的 dequeue，但我不知道该怎么做。

代码：

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)

Answer 1

我认为您的解决方案可以受益于更好的图形表示。特别是尝试为 BFS 保留一个邻居列表。我实际上在这里写了一个关于我用于流算法的图形表示的很长的答案

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

Edmonds–Karp 时间复杂度

Edmonds–Karp time complexity

python

max-flow

edmonds-karp