TheAlgorithms/Java · error · IllegalArgumentException

Costs must be non-negative

Error message

Costs must be non-negative

What it means

HungarianAlgorithm.validate throws this IllegalArgumentException when any cost[i][j] is negative. The Hungarian algorithm's potential/labeling math assumes non-negative costs; negative entries can break dual feasibility and produce incorrect assignments.

Source

Thrown at src/main/java/com/thealgorithms/graph/HungarianAlgorithm.java:145

        }
        return new Result(assignment, total);
    }

    private static void validate(int[][] cost) {
        if (cost == null || cost.length == 0) {
            throw new IllegalArgumentException("Cost matrix must not be null or empty");
        }
        int c = cost[0].length;
        if (c == 0) {
            throw new IllegalArgumentException("Cost matrix must have at least 1 column");
        }
        for (int i = 0; i < cost.length; i++) {
            if (cost[i] == null || cost[i].length != c) {
                throw new IllegalArgumentException("Cost matrix must be rectangular with equal row lengths");
            }
            for (int j = 0; j < c; j++) {
                if (cost[i][j] < 0) {
                    throw new IllegalArgumentException("Costs must be non-negative");
                }
            }
        }
    }
}

View on GitHub (pinned to fdfb9a395b)

Solutions

1. Shift all costs to non-negative by subtracting the minimum: cost[i][j] -= minCost.
2. Clamp: cost[i][j] = Math.max(0, val).
3. If using profit instead of cost, convert via cost = maxProfit - profit.

Example fix

// before
int[][] cost = { {-5, 2}, {3, 4} }; // negative cost

// after
int min = findMin(cost);
for (int i = 0; i < cost.length; i++)
    for (int j = 0; j < cost[0].length; j++)
        cost[i][j] -= min; // now all >= 0

int min = Integer.MAX_VALUE;
for (int[] row : cost) for (int v : row) min = Math.min(min, v);
if (min < 0) {
    for (int i = 0; i < cost.length; i++)
        for (int j = 0; j < cost[i].length; j++)
            cost[i][j] -= min;
}

boolean allNonNegative(int[][] cost) {
    for (int[] row : cost) for (int v : row) if (v < 0) return false;
    return true;
}

When it happens

Trigger: Passing a cost matrix containing any negative cell, e.g. a discount represented as a negative cost.

Common situations: Using negative costs for 'bonus' assignments instead of subtracting a constant. Signed cost values from input not normalized. Penalty subtraction producing negatives.

Related errors

• Capacities must be non-negative
• Capacities must be non-negative
• Cost matrix must not be null or empty
• Cost matrix must have at least 1 column
• Cost matrix must be rectangular with equal row lengths

AI-assisted analysis of TheAlgorithms/Java@fdfb9a395b (2026-08-13). Data as JSON: /api/errors/a72969fe8d7efc84. Report an issue: GitHub.