Edmonds–Karp algorithm: Difference between revisions

Revision as of 09:00, 13 September 2020

Revision as of 11:23, 2 November 2020

Line 33:

cur := q.pull()

'''for''' Edge e '''in''' graph[cur] '''do'''

'''if''' pred[e.t] = '''null''' '''and''' e.t ≠ s '''and''' e.cap > e.flow '''then'''

pred[e.t] := e

q.push(e.t)

'''if''' '''not''' (pred[t] = null) '''then'''

''(We found an augmenting path.''

Line 48:

e.rev.flow := e.rev.flow - df

flow := flow + df

'''until''' pred[t] = null ''(i.e., until no augmenting path was found)''

'''return''' flow