TheAlgorithms/Java · error · IllegalArgumentException

Weights must be -1 (no edge) or >= 0

Error message

Weights must be -1 (no edge) or >= 0

What it means

YensKShortestPaths uses -1 (NO_EDGE) as the sentinel for 'no edge' and requires all other weights to be non-negative (zero-weight edges are allowed). A value less than -1 is ambiguous — it is neither the sentinel nor a valid cost — and would corrupt Dijkstra's non-negative-weight assumption. The check rejects weights[i][j] < NO_EDGE.

Source

Thrown at src/main/java/com/thealgorithms/graph/YensKShortestPaths.java:124

        for (Path p : shortestPaths) {
            result.add(new ArrayList<>(p.nodes));
        }
        return result;
    }

    private static void validate(int[][] weights, int src, int dst, int k) {
        if (weights == null || weights.length == 0) {
            throw new IllegalArgumentException("Weights matrix must not be null or empty");
        }
        int n = weights.length;
        for (int i = 0; i < n; i++) {
            if (weights[i] == null || weights[i].length != n) {
                throw new IllegalArgumentException("Weights matrix must be square");
            }
            for (int j = 0; j < n; j++) {
                int val = weights[i][j];
                if (val < NO_EDGE) {
                    throw new IllegalArgumentException("Weights must be -1 (no edge) or >= 0");
                }
            }
        }
        if (src < 0 || dst < 0 || src >= n || dst >= n) {
            throw new IllegalArgumentException("Invalid src/dst indices");
        }
        if (k < 1) {
            throw new IllegalArgumentException("k must be >= 1");
        }
    }

    private static boolean startsWith(List<Integer> list, List<Integer> prefix) {
        if (prefix.size() > list.size()) {
            return false;
        }
        for (int i = 0; i < prefix.size(); i++) {
            if (!Objects.equals(list.get(i), prefix.get(i))) {
                return false;

View on GitHub (pinned to fdfb9a395b)

Solutions

1. Normalize the matrix before calling: replace your no-edge sentinel with -1 and ensure all real weights are >= 0.
2. If you need negative weights, this algorithm does not support them — use Bellman-Ford-based k-shortest-paths instead.
3. Add a sanitization pass: for each cell, if it represents 'no edge' set it to -1, else assert it >= 0.

Example fix

// before (uses -999 as no-edge)
int[][] w = buildMatrix(); // contains -999 and >=0 values
YensKShortestPaths.kShortestPaths(w, 0, n-1, 3);

// after
for (int i = 0; i < w.length; i++)
    for (int j = 0; j < w.length; j++)
        if (w[i][j] == -999) w[i][j] = -1; // align with NO_EDGE sentinel
YensKShortestPaths.kShortestPaths(w, 0, n-1, 3);

for (int i = 0; i < weights.length; i++) {
    for (int j = 0; j < weights.length; j++) {
        int v = weights[i][j];
        if (v != -1 && v < 0) {
            throw new IllegalArgumentException("weight at [" + i + "][" + j + "] is " + v + "; must be -1 or >= 0");
        }
    }
}
YensKShortestPaths.kShortestPaths(weights, src, dst, k);

When it happens

Trigger: Passing a matrix containing any value < -1, e.g. -2, -5, or Integer.MIN_VALUE. Common when a graph loader uses a different sentinel (like -999) or when an int underflow produces a negative weight.

Common situations: Mixing sentinel conventions (another library uses Integer.MIN_VALUE or a large negative for no-edge), parsing a weighted graph where absent edges default to 0 and present edges were negated by a sign error, or reusing a matrix from a different algorithm that allows arbitrary weights.

Related errors

• Weights matrix must not be null or empty
• Weights matrix must be square
• k must be >= 1
• adjacencyList size must equal vertexCount
• Matrix must be square

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