Content deleted Content added
Changed the markup language to "math" in the "Definitions and notations" section |
Added new Initialization subsection to the Operations section. Performed minor updates. |
||
Line 57:
===Operations===
====Initialization====
The algorithm starts by creating a residual graph, initializing the preflow values to zero and performing a set of saturating push operations on residual edges exiting the source, {{nowrap|(''s'', ''v'') where ''v'' ∈ ''V'' \ {''s''}}}. Similarly, the label heights are initialized such that the height at the source is in the number of vertices in the graph, {{nowrap|''h''(''s'') {{=}} {{!}}''V''{{!}}}}, and all other vertices are given a height of zero. Once the initialization is complete, the algorithm repeatedly performs either the push or relabel operations against active vertices until no applicable operation can performed.
====Push====
The push operation applies on an admissible out-edge {{nowrap|(''u'', ''v'')}} of an active vertex ''u'' in {{nowrap|''G<sub>f</sub>''}}. It moves
push(u, v):
Line 69 ⟶ 73:
e[v] += Δ
A push operation that causes {{nowrap|''f''(''u'', ''v'')}} to reach {{nowrap|''c''(''u'', ''v'')}} is called a ''saturating'' push
====Relabel====
The relabel operation applies on an active vertex ''u'' without any admissible out-edges in {{nowrap|''G<sub>f</sub>''}}. It modifies {{nowrap|''h''(''u'')}} to the minimum value such that an admissible out-edge is created. Note that this always increases {{nowrap|''h''(''u'')}} and never creates a steep edge, which is
relabel(u):
| |||