Edmonds–Karp algorithm: Difference between revisions

Revision as of 02:21, 17 November 2005

Revision as of 12:08, 17 December 2005

Line 1:

In [[computer science]] and [[graph theory]], the '''Edmonds-Karp algorithm''' is an implementation of the [[Ford-Fulkerson algorithm|Ford-Fulkerson method]] for computing the [[maximum flow problem|maximum flow]] in a [[flow network]]. The distinguishing feature is that the shortest augmenting path is used at each step, which guarantees that the computation will terminate. In most implementations, the shortest augmenting path is found using a [[breadth-first search]].

The Edmonds-Karp algorithm runs in [[Big O notation|O]](VE²) time, where V is the number of vertices and E is the number of edges in the network. Hence it is asymptotically slower than the [[relabel-to-front algorithm]], which runs in [[Big O notation|O]](V³), but it is often faster in practise for [[sparse graph]]s.

The algorithm was first published by a Russian scientist, Dinic, in 1970, and later, independently, by Edmonds and Karp who published it in 1972. Dinic' algorithm includes additional techniques that reduce the running time to [[Big O notation|O]](EV²).

==Sample implementation==

[[Python programming language|Python]] implementation:

def edmonds_karp(C, source, sink):

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

F = [[0] * n for _ 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 path:

break

flow = Inf # ''traverse path to find smallest capacity''

for i 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 i 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):

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

P[source] = source

queue = [source]

while len(queue):

u = queue.pop(0)

for v in xrange(len(C)):

if C[u][v] - F[u][v] > 0 and P[v] == -1:

P[v] = u

queue.append(v)

if v == sink:

path = []

while True:

path.insert(0, v)

if v == source:

break

v = P[v]

return path

return None

==References==