Munkres Algorithm does not return optimal results

[malibu]

For the following cost matrix., see the output. An optimal assignment should swap [5] and [3] for minimal cost assignment.

{
double [][] cost = new double[6][];   
            cost[0] = new double[4] { 10,20,2,40 };
            cost[1] = new double[4] { 10, Double.MaxValue, 3, Double.MaxValue };
            cost[2] = new double[4] { 20, 10, 60, 1 };
            cost[3] = new double[4] { 20, Double.MaxValue, 25, Double.MaxValue };
            cost[4] = new double[4] { Double.MaxValue, 40, 60, Double.MaxValue };
            cost[5] = new double[4] { 0, 19, Double.MaxValue, 2 };
            var munk = new Munkres(cost);
            munk.Minimize();
            var assignments = munk.Solution;
}

Any clues?

[DvdKhl]

For the given example above the minimum cost is 22 with the solution Vector {2, 0, 1 NaN, NaN, 3}. The implemented algorithm doesn't seem to work with non quadratic matrices.

If you however transform your matrix to an equivalent quadratic one it seems to work:

var inf = double.PositiveInfinity;
double[][] cost = new double[6][];
cost[0] = new [] { 10d, 20d, 2d, 40d, inf, inf };
cost[1] = new [] { 10d, inf, 3d, inf, inf, inf };
cost[2] = new [] { 20d, 10d, 60d, 1d, inf, inf };
cost[3] = new [] { 20d, inf, 25d, inf, inf, inf };
cost[4] = new [] { inf, 40d, 60d, inf, inf, inf };
cost[5] = new [] { 0d, 19d, inf, 2d, inf, inf };
var munk = new Munkres(cost);
munk.Minimize();
var assignments = munk.Solution;

Produces the solution vector I mentioned above.

[DvdKhl]

Sadly I've found another wrong result even with quadratic matrices:

var inf = double.PositiveInfinity;
double[][] cost = new double[6][];
cost[0] = new[] { 10d, 20d,  2d, 40d, inf,  1d };
cost[1] = new[] { 10d, inf,  3d, inf, inf, inf };
cost[2] = new[] { 20d, 10d, 60d,  1d, inf, inf };
cost[3] = new[] { 20d, inf, 25d, inf, inf, inf };
cost[4] = new[] { inf, inf, inf, inf, inf, inf };
cost[5] = new[] {  0d, 19d, inf,  2d,  1d, inf };

var munk = new Munkres(cost);
var success = munk.Minimize();
var assignments = munk.Solution;

Delivers {5,2,3,0,NaN,0} which is obviously wrong since 0 is used twice. The last index should be 4 for the optimal result.