cynicphoenix / successive-shortest-path-algorithm Goto Github PK

Start with M equal to the empty set
Define p(x) = 0 for x 𝛜 X, and p(y) = min(e) into y ce for y 𝛜 Y
While M is not a perfect matching..,
	Compute shortest path distances d
P ← shortest alternating path using reduced cost & Dijkstra’s Algo.
Augment along P to produce a new matching M’.
foreach v ∈ X ∪ Y: p(v) ← p(v) + d(v).
Endwhile;