pythonmax-flowedmonds-karp

Edmonds–Karp time complexity


I am trying to implement a version of the Edmonds–Karp algorithm for an undirected graph. The code below works, but it is very slow when working with big matrices.

Is it possible to get the Edmonds–Karp algorithm to run faster, or should I proceed to another algorithm, like "Push Relabel"? I have though of some kind of dequeue working with the bfs, but I don't know how to do that.

The code:

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)

Solution

  • I think your solution can benefit from better graph representation. In particular try to keep a list of neighbours for the BFS. I actually wrote a quite long answer on the graph representation I use for flow algorithms here https://stackoverflow.com/a/23168107/812912

    If your solution is still too slow I would recommend switching to Dinic's algorithm it has served me well in many tasks.