Hungarian algorithm doesn't work

[tintor]

For input cost matrix (w -> j [cost]): 0 -> 0 [19.0] 0 -> 1 [18.0] 0 -> 2 [17.0] 1 -> 0 [26.0] 1 -> 1 [25.0] 1 -> 2 [24.0] 2 -> 0 [0.0] 2 -> 1 [Infinity] 2 -> 2 [Infinity]

It returns: 0 -> 0 [19.0] 1 -> 1 [25.0] 2 -> 2 [Infinity]

While the min cost solution is: 0 -> 1 [18.0] 1 -> 2 [24.0] 2 -> 0 [0.0] OR 0 -> 2 [17.0] 1 -> 1 [25.0] 2 -> 0 [0.0]

[KevinStern]

Hi,

I'm not seeing the issue that you're describing; I wrote the following test and it passes:

  @Test
  public void test4() {
    double[][] matrix = new double[][] {new double[] { 19, 18, 17},
        new double[] { 26, 25, 24},
        new double[] { 0, Double.MAX_VALUE, Double.MAX_VALUE}};
    HungarianAlgorithm b = new HungarianAlgorithm(matrix);
    int[] match = b.execute();
    Assert.assertTrue(Arrays.equals(new int[] { 1, 2, 0 }, match));
    Assert.assertEquals(42, computeCost(matrix, match), 0.0000001);
  }

Could you provide some code that uses HungarianAlgorithm.java and produces the wrong result if you still believe there is a bug in the implementation?

Thanks!

Kevin