Content deleted Content added
Each BFS iteration only seeks to find a shortest augmenting path. Therefore the BFS loop can terminate once a path from s to t is found. Further iterations will not modify pred entries that are already set, and therefore have absolutely no effect on the result. |
Fixed a typo |
||
Line 27:
q.push(s)
pred := '''array'''(graph.length)
'''while''' '''not''' empty(q) '''and''' pred[
cur := q.pop()
'''for''' Edge e '''in''' graph[cur] '''do'''
| |||