Content deleted Content added
Added free to read link in citations with OAbot #oabot |
|||
Line 10:
{{Wikibooks|Algorithm implementation|Graphs/Maximum flow/Edmonds-Karp|Edmonds-Karp}}
'''algorithm''' EdmondsKarp '''is'''
'''input''':
graph ''(graph[v] should be the list of edges coming out of vertex v in the''
Line 32:
'''while''' '''not''' empty(q)
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)
''(We found an augmenting path.''
'' See how much flow we can send)''
df := '''∞'''
'''for''' (e := pred[t]; e ≠ null; e := pred[e.s]) '''do'''
df := '''min'''(df, e.cap - e.flow)
''(And update edges by that amount)''
'''for''' (e := pred[t]; e ≠ null; e := pred[e.s]) '''do'''
e.flow := e.flow + df
e.rev.flow := e.rev.flow - df
| |||