Wikipedia

Blossom algorithm: Difference between revisions

Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
m added "end if"s for all if statements in find_augmenting_path algorithm
m →Finding an augmenting path: Commented out the line that does nothing in find_augmenting_path algorithm, re-numbered lines
Line 112:
B13 '''else'''
B14 '''if''' ''distance( w, root( w ) )'' is odd '''then'''
B15 do // Do nothing.
B16B15 '''else'''
B17B16 '''if''' ''root( v )'' ≠ ''root( w )'' '''then'''
// Report an augmenting path in F <math>\cup</math> { ''e'' }.
B18B17 ''P'' ← path ( ''root''( ''v'' ) → ... → ''v'' ) → ( ''w'' → ... → ''root''( ''w'' ) )
B19B18 '''return''' ''P''
B20B19 '''else'''
// Contract a blossom in ''G'' and look for the path in the contracted graph.
B21B20 ''B'' ← blossom formed by ''e'' and edges on the path ''v'' → ''w'' in ''T''
B22B21 ''G’, M’'' ← contract ''G'' and ''M'' by ''B''
B23B22 ''P’'' ← ''find_augmenting_path''( ''G’'', ''M’'' )
B24B23 ''P'' ← lift ''P’'' to ''G''
B25B24 '''return''' ''P''
B26B25 '''end if'''
B27B26 '''end if'''
B28B27 '''end if'''
B29B28 mark edge ''e''
B30B29 '''end while'''
B31B30 mark vertex ''v''
B32B31 '''end while'''
B33B32 '''return''' empty path
B34B33 '''end function'''
 
===Examples===
Retrieved from "https://en.wikipedia.org/wiki/Blossom_algorithm"