Edmonds–Karp algorithm: Difference between revisions

Revision as of 16:42, 31 July 2006

Revision as of 05:51, 3 August 2006

Line 25:

'''def''' edmonds_karp(C, source, sink):

n = len(C) # ''# C is the capacity matrix''

F = [[0] * n '''for''' _i '''in''' xrange(n)]

# ''# residual capacity from u to v is C[u][v] - F[u][v]''

'''while''' True:

path = bfs(C, F, source, sink)

'''if not''' not path:

'''break'''

flow = Inffloat("infinity")
# ''# traverse path to find smallest capacity''

'''for''' i(u,v) '''in''' xrange(len(path) - 1):

u,v = path[i], path[i+1]

flow = min(flow, C[u][v] - F[u][v])

# ''# traverse path to update flow''

'''for''' iu,v '''in''' range(len(path) - 1):

u,v = path[i], path[i+1]

F[u][v] += flow

F[v][u] -= flow

'''return''' sum([F[source][i] '''for''' i '''in''' xrange(n)])

'''def''' bfs(C, F, source, sink):

Pqueue = [-1source] * len(C) # ''parent in search tree''

P[source]paths = {source: []}

queue = [source]

'''while''' queue:

u = queue.pop(0)

'''for''' v '''in''' xrange(len(C)):

'''if''' C[u][v] - F[u][v] > 0 '''and''' P[v] =='''not''' -1in paths:

Ppaths[v] = paths[u] + [(u,v)]

queue.append(v)

'''if''' v == sink:

path ='''return''' paths[v]

'''while''' True:queue.append(v)

path.insert(0, v)

if v == source:

'''break'''

v = P[v]

'''return''' path

'''return''' None