Page 1 of 1

Maximum Bipartite Matching

Posted: Wed Jul 09, 2008 3:34 pm
by Liglogthepanda
A question for those familiar with graph theory or the matching type of algorithms:

So I have a bipartite graph and I want to perform a maximum matching operation on it. If I call the 'left hand side' "items" and the 'right hand side' "bins", I want to input which items can fit in which bins, and be output with "Item A goes into Bin X, Item B in Bin Y", etc.

Obviously I've simplified this. But the PHP will need to include Dijkstra's algorithm somewhere (which I can understand with pen-and-paper but not in code).

I can't think of any way to do this ... at all. Help!