Hungarian Algorithm - Arbitrary Assignments

I've looked at several explanations of the Hungarian Algorithm for solving the Assignment Problem and the vast majority of these cover only very simplistic cases.

The most understandable explanation I've found is a YouTube video.

I can code the algorithm but I'm concerned about one special case. If you watch the video, the relevant case is explained from 31:55 to 37:42, but I’ll explain it below.

I should first mention that I will be dealing with a 300 x 300 matrix, so visual inspection is out of the question. Additionally, I need to find all minimum assignments. In other words, if there are multiple assignments that produce the same minimum value, I need to find them all.

Here's the particular case that I'm concerned about. You can see this explained in the YouTube video but I’ll go over it here. We start with this matrix:

3   1   1   4
4   2   2   5
5   3   4   8
4   2   5   9

When we reduce the rows and columns, we get this:

0   0   0   0
0   0   0   0
0   0   1   2
0   0   3   4

(Let me mention that I can visually see there are 4 solutions to this matrix and the total score is 13.)

Given the above reduced matrix, there are no unique zeros in any row or column, so, according to the algorithm described in the video, I can arbitrarily select any zero element for assignment, so I select (1,1).

I’ll mark the assigned zero with an asterisk and I’ll put an “x” next to those zeros in the rows and columns that are no longer available for consideration. Now we have this:

0*  0x  0x  0x
0x  0   0   0
0x  0   1   2
0x  0   3   4

Next, we continue examining rows for a unique zero. We find one at (3,2) so we mark it with an asterisk and mark the unavailable zeros with "x":

0*  0x  0x  0x
0x  0x  0   0
0x  0*  1   2 
0x  0x  3   4

Next, we start looking for unique zeros in the columns (since all rows have been exhausted). We find column three has a unique zero at (2,3) so we mark it:

```
0* 0x 0x 0x
0x 0x 0* 0x
0x 0* 1

See Finding all minimum-cost perfect matchings in Bipartite graphs.

Once you run the Hungarian Algorithm, you can use the result to

• find all "admissable" edges. Roughly speaking, admissable edges are those that are part of some min-cost perfect matching (potentially with a few extras).

• generate perfect matchings of the subgraph of just the admissable edges. During this step, you don't need to look for min-cost perfect matchings. By the choice of admissable edges, any perfect matching of the subgraph is automatically a min-cost perfect matching of the original graph. This step is much easier than explicitly looking for min-cost perfect matchings.

StackExchange Computer Science Q#62436, answer score: 3