detailed hungarian algorithm(assignment problem) question

I have implemented the hungarian algorithm, a solution to the assignment problem, as described by this article, but it fails on a few percent of random costs matrices.

I've spent weeks debugging it(I started when I asked this question, not full time though). I took random cost matrices for which the algorithm fails and performed the algorithm with good old pen and paper, a开发者_开发技巧nd compared that with my implementation to see what went wrong. This led me to a few bugs which I've corrected now, but I have encountered an example for which I do not get the right solution when solving it by hand. For anyone who is interested: the costmatrix of that example is {{0,6,4,3},{3,2,1,2},{0,7,6,4},{3,8,5,3}}, for which the correct solution has the sum of 9=4+2+0+3(in that order). In that example there is eventually a matched edge not on the equality subgraph, and I think that is impossible, indicating something is wrong.

Either I don't fully understand the solution, which is a viable option, or an extremely subtle bug in the presented solution, which I will elaborate on below.

I realize I have to introduce some terminology, but since this is a detailed question I am not going to explain all concepts in full detail, as anyone needing that explanation probably wouldn't be able to answer my question anyway.

• The input of the problem is a weighted complete bipartite graph with n nodes on each partition.
• The presented method specifies to find n augmenting paths.
• An augmenting path is an alternating path starting and ending at a unmatched nodes.
• An alternating path is a path alternating between matched an unmatched edges on the equality subgraph.
• These alternating paths are grown in a breadth-first manner, stopping only when either:
  • An augmenting path is found or
  • the alternating paths cannot be grown any further.
• And a crucial fact to the possible bug: the algorithm remembers what nodes the alternating paths have encountered, which affects the algorithm in a part irrelevant to this question.

When an augmented path is found, the presented method says to stop growing the alternating paths. I believe this is incorrect. I think all alternating paths need to be grown up to the cost of the found augmented path. Notice that the alternating paths are grown in a breadth first manner, so this only grows paths whose costs can tie with the found path. This small change might result in some nodes being marked as 'visited by alternating path' which otherwise wouldn't have been marked, which affect the algorithm further on.

The actual question: Should I consider alternating paths with costs equal to the costs of the augmented path (and starting at the same node) explored? This is contrary to the presented method, which says to stop as soon as an augmented path is found, regardless of any ties in costs with other paths.

---

Looking at the presentation of the Hungarian algorithm in "The Stanford GraphBase" you can track its progress towards a solution as adding a constant to every cell in a row of the cost matrix, or every cell in a column of the cost matrix, and see that you have a solution when you have a complete set of independent zeros in the altered matrix.

I have read just once the paper you refer to. Is it the case that finding an augmenting path allows you to increase the number of independent zeros in the altered matrix? If so, then finding n augmenting paths, as in their Figure 3 step 2, will find a good solution, because you must then have n independent zeros. If so, then you can check your implementation of the algorithm by checking that each augmenting path found adds an independent zero, even in the case when there are other paths that it could have found but stopped short of finding.