Given:
- Bipartite Graph G(V = X βͺ Y, E)
- For every edge e π E, Ce is the cost of the edge.
- |X| = |Y| = n
- There exist a perfect matching.
- Ce β₯ 0 β e π E.
Goal: We need to find the minimum cost bipartite matching.
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;
- Amit Srivastava
- Gyan Prakash Singh