Push–relabel maximum flow algorithm: Difference between revisions

Revision as of 06:23, 11 April 2014

Revision as of 12:35, 11 April 2014

Line 69:

===Description===

Since {{nowrap|''h''(''s'') {{=}} {{!}}''V''{{!}}}}, {{nowrap|''h''(''t'') {{=}} 0}}, and there isare notno pathpaths longer than {{nowrap|({{!}}''V''{{!}} − 1)}} in {{nowrap|''G_f''}}, in order for {{nowrap|''h''(''s'')}} to satisfy the valid labeling condition, ''s'' must be disconnected from ''t''. At initialization, the algorithm fulfills this requirement by creating a preflow ''f'' that saturates all out-edges of ''s'', after which {{nowrap|''h''(''u'') {{=}} 0}} is trivially valid for all {{nowrap|''v'' ∈ ''V'' \ {''s'', ''t''}}}.

After initialization, the algorithm repeatedly executes an applicable push or relabel operation until no such operations apply, at which point the preflow has been converted into a maximum flow.