{"record":{"id":"8ffaa7843f4475fe","repo":"TheAlgorithms/Java","slug":"weights-must-be-1-no-edge-or-0","errorCode":null,"errorMessage":"Weights must be -1 (no edge) or >= 0","messagePattern":"Weights must be -1 \\(no edge\\) or >= 0","errorType":"validation","errorClass":"IllegalArgumentException","httpStatus":null,"severity":"error","filePath":"src/main/java/com/thealgorithms/graph/YensKShortestPaths.java","lineNumber":124,"sourceCode":"        for (Path p : shortestPaths) {\n            result.add(new ArrayList<>(p.nodes));\n        }\n        return result;\n    }\n\n    private static void validate(int[][] weights, int src, int dst, int k) {\n        if (weights == null || weights.length == 0) {\n            throw new IllegalArgumentException(\"Weights matrix must not be null or empty\");\n        }\n        int n = weights.length;\n        for (int i = 0; i < n; i++) {\n            if (weights[i] == null || weights[i].length != n) {\n                throw new IllegalArgumentException(\"Weights matrix must be square\");\n            }\n            for (int j = 0; j < n; j++) {\n                int val = weights[i][j];\n                if (val < NO_EDGE) {\n                    throw new IllegalArgumentException(\"Weights must be -1 (no edge) or >= 0\");\n                }\n            }\n        }\n        if (src < 0 || dst < 0 || src >= n || dst >= n) {\n            throw new IllegalArgumentException(\"Invalid src/dst indices\");\n        }\n        if (k < 1) {\n            throw new IllegalArgumentException(\"k must be >= 1\");\n        }\n    }\n\n    private static boolean startsWith(List<Integer> list, List<Integer> prefix) {\n        if (prefix.size() > list.size()) {\n            return false;\n        }\n        for (int i = 0; i < prefix.size(); i++) {\n            if (!Objects.equals(list.get(i), prefix.get(i))) {\n                return false;","sourceCodeStart":106,"sourceCodeEnd":142,"githubUrl":"https://github.com/TheAlgorithms/Java/blob/fdfb9a395b310167a66bd29e311e36e0e3e9b964/src/main/java/com/thealgorithms/graph/YensKShortestPaths.java#L106-L142","documentation":"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.","triggerScenarios":"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.","commonSituations":"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.","solutions":["Normalize the matrix before calling: replace your no-edge sentinel with -1 and ensure all real weights are >= 0.","If you need negative weights, this algorithm does not support them — use Bellman-Ford-based k-shortest-paths instead.","Add a sanitization pass: for each cell, if it represents 'no edge' set it to -1, else assert it >= 0."],"exampleFix":"// before (uses -999 as no-edge)\nint[][] w = buildMatrix(); // contains -999 and >=0 values\nYensKShortestPaths.kShortestPaths(w, 0, n-1, 3);\n\n// after\nfor (int i = 0; i < w.length; i++)\n    for (int j = 0; j < w.length; j++)\n        if (w[i][j] == -999) w[i][j] = -1; // align with NO_EDGE sentinel\nYensKShortestPaths.kShortestPaths(w, 0, n-1, 3);","handlingStrategy":"validation","validationCode":"for (int i = 0; i < weights.length; i++) {\n    for (int j = 0; j < weights.length; j++) {\n        int v = weights[i][j];\n        if (v != -1 && v < 0) {\n            throw new IllegalArgumentException(\"weight at [\" + i + \"][\" + j + \"] is \" + v + \"; must be -1 or >= 0\");\n        }\n    }\n}\nYensKShortestPaths.kShortestPaths(weights, src, dst, k);","typeGuard":null,"tryCatchPattern":null,"preventionTips":["Standardize on -1 as the 'no edge' sentinel across your graph pipeline.","If your data source uses another sentinel (e.g. Integer.MIN_VALUE, -999), normalize at load time.","Do not feed graphs with negative weights to Dijkstra-based algorithms; choose Bellman-Ford variants instead."],"tags":["graph","validation","sentinel","negative-weight","yens","dijkstra"],"backgroundTag":null,"analyzedSha":"fdfb9a395b310167a66bd29e311e36e0e3e9b964","analyzedAt":"2026-08-13T23:36:13.315Z","schemaVersion":2},"datasetVersion":"2026-08-14T05:17:29.042Z"}