Edmonds algorithm

Build a graph bipartite (the elements on the left are connected only to elements on the right by arcs, the elements on the right have no outgoing connection) such that the elements on the left are the machines and the elements on the right are the tasks to be perform. Bows are of capacity 1 and cost according to the assignment table. If a flow passes through an edge (i,j), this amounts to saying that machine i performs task j.

In order to complete the bipartite graph to make it a flow problem, each left element is linked as a terminal vertex to a fictitious source. Each line element is bound as an origin vertex to a fictitious well. All these arcs have capacity 1 and cost 0. In order to solve the assignment problem, we apply a algorithm of maximum flow at minimal cost to the constructed bipartite graph.