Content deleted Content added
updated broken link to Kolmogorov's implementation |
Simonpratt (talk | contribs) m added "end if"s for all if statements in find_augmenting_path algorithm |
||
Line 111:
B12 add edges { ''v'', ''w'' } and { ''w'', ''x'' } to the tree of ''v''
B13 '''else'''
B14 '''if''' ''distance( w, root( w ) )'' is odd '''then'''
B15 do nothing
B16 '''else'''
B17 '''if''' ''root( v )'' ≠ ''root( w )'' '''then'''
// Report an augmenting path in F <math>\cup</math> { ''e'' }.
B18 ''P'' ← path ( ''root''( ''v'' ) → ... → ''v'' ) → ( ''w'' → ... → ''root''( ''w'' ) )
B19 '''return''' ''P''
B20 '''else'''
// Contract a blossom in ''G'' and look for the path in the contracted graph.
B21 ''B'' ← blossom formed by ''e'' and edges on the path ''v'' → ''w'' in ''T''
B22 ''G’, M’'' ← contract ''G'' and ''M'' by ''B''
B23 ''P’'' ← ''find_augmenting_path''( ''G’'', ''M’'' )
B24 ''P'' ← lift ''P’'' to ''G''
B25 '''return''' ''P''
B26 '''end if'''
B27
B28 '''end
B29 mark
B30 '''end while'''
B31 mark vertex ''v'
B32 '''end
B33 '''return''' empty path
B34 '''end function'''
===Examples===
| |||