The below test case shows this in the form of the smallest case that happens (N=4) on one of my specific matrix.
When calculating the solution for the whole matrix, without assertions, even weirder things happen, as then at some point DijkstraSP
's constructor complains about negative edge โ a closer look reveals it's "negative zero" value, so this might be potentially another source of bugs.
I suspect the two or more same cost values in the matrix, although those should also trigger an error for N=3.
import org.junit.Before;
import org.junit.Test;
import edu.princeton.cs.algs4.AssignmentProblem;
public class TestNegativeZeroAssignment {
/*
5.1155, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 4.99745, 5.1155, 5.1155, 5.1155, 5.1155, 5.1155
168.2473, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 164.36467, 168.2473, 168.2473, 168.2473, 168.2473, 168.2473
238.9088, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 233.39552, 238.9088, 238.9088, 238.9088, 238.9088, 238.9088
573.4521000000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 560.2185900000001, 573.4521000000001, 573.4521000000001, 573.4521000000001, 573.4521000000001, 573.4521000000001
552.9472000000001, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 540.18688, 552.9472000000001, 552.9472000000001, 552.9472000000001, 552.9472000000001, 552.9472000000001
498.0872, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 486.59288000000004, 498.0872, 498.0872, 498.0872, 498.0872, 498.0872
564.6784000000001, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 551.64736, 564.6784000000001, 564.6784000000001, 564.6784000000001, 564.6784000000001, 564.6784000000001
338.6162, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 330.80198, 338.6162, 338.6162, 338.6162, 338.6162, 338.6162
502.53970000000004, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 490.94263, 502.53970000000004, 502.53970000000004, 502.53970000000004, 502.53970000000004, 502.53970000000004
721.6495, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 704.99605, 721.6495, 721.6495, 721.6495, 721.6495, 721.6495
692.3683000000001, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 676.39057, 692.3683000000001, 692.3683000000001, 692.3683000000001, 692.3683000000001, 692.3683000000001
615.3081999999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 601.1087799999999, 615.3081999999999, 615.3081999999999, 615.3081999999999, 615.3081999999999, 615.3081999999999
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0
*/
long[][] bits = new long[][] {
new long[] { 4617445559400841347L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617312646916838575L, 4617445559400841347L, 4617445559400841347L, 4617445559400841347L, 4617445559400841347L, 4617445559400841347L },
new long[] { 4640123692170381728L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4639987084271778466L, 4640123692170381728L, 4640123692170381728L, 4640123692170381728L, 4640123692170381728L, 4640123692170381728L },
new long[] { 4642609872678736731L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642415891383786815L, 4642609872678736731L, 4642609872678736731L, 4642609872678736731L, 4642609872678736731L, 4642609872678736731L },
new long[] { 4648255353834361901L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648138950649391581L, 4648255353834361901L, 4648255353834361901L, 4648255353834361901L, 4648255353834361901L, 4648255353834361901L },
new long[] { 4648074990826550828L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4647962749864837686L, 4648074990826550828L, 4648074990826550828L, 4648074990826550828L, 4648074990826550828L, 4648074990826550828L },
new long[] { 4647470058880353121L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647267848664459070L, 4647470058880353121L, 4647470058880353121L, 4647470058880353121L, 4647470058880353121L, 4647470058880353121L },
new long[] { 4648178179553012955L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648063557312996841L, 4648178179553012955L, 4648178179553012955L, 4648178179553012955L, 4648178179553012955L, 4648178179553012955L },
new long[] { 4644664615379664057L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644527146167632061L, 4644664615379664057L, 4644664615379664057L, 4644664615379664057L, 4644664615379664057L, 4644664615379664057L },
new long[] { 4647548388088715884L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647344370275705768L, 4647548388088715884L, 4647548388088715884L, 4647548388088715884L, 4647548388088715884L, 4647548388088715884L },
new long[] { 4649558911950411268L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649412426655070578L, 4649558911950411268L, 4649558911950411268L, 4649558911950411268L, 4649558911950411268L, 4649558911950411268L },
new long[] { 4649301351791409392L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649160810192045668L, 4649301351791409392L, 4649301351791409392L, 4649301351791409392L, 4649301351791409392L, 4649301351791409392L },
new long[] { 4648623523983508740L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648498624564327339L, 4648623523983508740L, 4648623523983508740L, 4648623523983508740L, 4648623523983508740L, 4648623523983508740L },
new long[] { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L },
new long[] { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L },
new long[] { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L },
new long[] { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L },
new long[] { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L },
new long[] { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L },
new long[] { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L },
new long[] { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L },
new long[] { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L },
new long[] { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L },
new long[] { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L },
new long[] { 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L }
};
double[][] weights;
// this N is the minimal that trigger an exception:
// java.lang.AssertionError: Dual variables are not feasible
// at edu.princeton.cs.algs4.AssignmentProblem.<init>(AssignmentProblem.java:80)
int maxN = 4;
@Before
public void makeWeights() {
int N = Math.min(maxN, bits.length);
weights = new double[N][];
for (int i = 0; i < N; ++i) {
weights[i] = new double[N];
for (int j = 0; j < N; ++j) {
weights[i][j] = Double.longBitsToDouble(bits[i][j]);
}
}
}
@Test
public void testAssignmentProblem() {
AssignmentProblem ap = new AssignmentProblem(weights);
}
}