For each vertex from left part (workers) find the minimal outgoing edge and subtract its weight from all weights connected with this vertex. Actually, this step is not necessary, but it decreases the number of main cycle iterations. Find the maximum matching using only 0-weight edges (for this purpose you can use max-flow algorithm, augmenting path algorithm, etc.). Step 2) Let and adjust the weights using the following rule: Step 3) Repeat Step 1 until solved.But there is a nuance here; finding the maximum matching in step 1 on each iteration will cause the algorithm to become O(n5).In order to avoid this, on each step we can just modify the matching from the previous step, which only takes O(n2) operations.
In other words, it only includes those edges from the bipartite matching which allow the vertices to be perfectly feasible.
Now we’re ready for the theorem which provides the connection between equality subgraphs and maximum-weighted matching: is called alternating if its edges alternate between M and E\M.
Our goal is to complete all jobs minimizing total inputs, while assigning each worker to exactly one job and vice versa. Small example just to make things clearer: This problem is known as the assignment problem.
The assignment problem is a special case of the transportation problem, which in turn is a special case of the min-cost flow problem, so it can be solved using algorithms that solve the more general cases.
The only thing in code that hasn't been explained yet is the procedure that goes after labels are updated.
Say we've updated labels and now we need to complete our alternating tree; to do this and to keep algorithm in O(n3) time (it's only possible if we use each edge no more than one time per iteration) we need to know what edges should be added without iterating through all of them, and the answer for this question is to use BFS to add edges only from those vertices in Y, that are not in T and for which slack[y] = 0 (it's easy to prove that in such way we'll add all edges and keep algorithm to be O(n3)).
See picture below for explanation: At last, here's the function that implements Hungarian algorithm: To see all this in practice let's complete the example started on step 0.| Build alternating tree V| Augmenting V path found| Build V alternating tree| Update V labels(Δ=1)| Build alternating V tree| Update V labels(Δ=1)→| Build V alternating tree| Augmenting V path found| Build V alternating tree| Update labels V (Δ=2)| Build V alternating tree| Update labels V (Δ=1)| Build V alternating tree| Augmenting V path found Optimalmatching found Finally, let's talk about the complexity of this algorithm.
On each iteration we increment matching so we have n iterations.
(For example, (W4, J4, W3, J3, W2, J2) and (W4, J1, W1) are alternating paths)If the first and last vertices in alternating path are exposed, it is called (because we can increment the size of the matching by inverting edges along this path, therefore matching unmatched edges and vice versa). And now let’s illustrate these steps by considering an example and writing some code.
((W4, J4, W3, J3, W2, J2) – augmenting alternating path)A tree which has a root in some exposed vertex, and a property that every path starting in the root is alternating, is called an . Find(1)and replace existing labeling with the next one:(2)Now replace with Step 3. As an example we’ll use the previous one, but first let’s transform it to the maximum-weighted matching problem, using the second method from the two described above.