TheAlgorithms/Java · error · IllegalArgumentException

Source and sink must be valid vertex indices

Error message

Source and sink must be valid vertex indices

What it means

Dinic.maxFlow throws this IllegalArgumentException when the source or sink vertex index falls outside the valid range [0, n) for a capacity matrix of size n×n. The check runs after the matrix is validated for squareness and non-negative capacities, so it guards only index bounds. It ensures the algorithm never indexes residual/level arrays out of range.

Source

Thrown at src/main/java/com/thealgorithms/graph/Dinic.java:53

     *     indices invalid
     */
    public static int maxFlow(int[][] capacity, int source, int sink) {
        if (capacity == null || capacity.length == 0) {
            throw new IllegalArgumentException("Capacity matrix must not be null or empty");
        }
        final int n = capacity.length;
        for (int i = 0; i < n; i++) {
            if (capacity[i] == null || capacity[i].length != n) {
                throw new IllegalArgumentException("Capacity matrix must be square");
            }
            for (int j = 0; j < n; j++) {
                if (capacity[i][j] < 0) {
                    throw new IllegalArgumentException("Capacities must be non-negative");
                }
            }
        }
        if (source < 0 || sink < 0 || source >= n || sink >= n) {
            throw new IllegalArgumentException("Source and sink must be valid vertex indices");
        }
        if (source == sink) {
            return 0;
        }

        // residual capacities
        int[][] residual = new int[n][n];
        for (int i = 0; i < n; i++) {
            residual[i] = Arrays.copyOf(capacity[i], n);
        }

        int[] level = new int[n];
        int flow = 0;
        while (bfsBuildLevelGraph(residual, source, sink, level)) {
            int[] next = new int[n]; // current-edge optimization
            int pushed;
            do {
                pushed = dfsBlocking(residual, level, next, source, sink, Integer.MAX_VALUE);

View on GitHub (pinned to fdfb9a395b)

Solutions

1. Verify source and sink are in [0, capacity.length - 1] before calling.
2. Ensure the capacity matrix dimension equals the total vertex count, including isolated vertices.
3. If your graph uses 1-based labels externally, convert to 0-based indices before calling.
4. Check that source != sink (though that returns 0, not an error) and that both are legitimate vertices.

Example fix

// before
int flow = Dinic.maxFlow(cap, startNode, endNode); // startNode/endNode are 1-based

// after
int flow = Dinic.maxFlow(cap, startNode - 1, endNode - 1); // convert to 0-based

if (source < 0 || sink < 0 || source >= capacity.length || sink >= capacity.length) {
    throw new IllegalArgumentException("Invalid source/sink for matrix of size " + capacity.length);
}

boolean validIndices(int[][] cap, int s, int t) {
    return cap != null && s >= 0 && t >= 0 && s < cap.length && t < cap.length;
}

When it happens

Trigger: Calling Dinic.maxFlow(capacity, source, sink) where source or sink is negative, or >= capacity.length. Also fires when the matrix was built for a different vertex count than the indices imply.

Common situations: Zero-indexed vs one-indexed confusion (passing 1-based vertex labels). Building the capacity matrix from an edge list but forgetting to include isolated vertices, making n smaller than the largest vertex id. Off-by-one when computing sink as the last node index.

Related errors

• Source and sink must be valid vertex indices
• Source and sink must be valid vertex indices
• Invalid number of vertices or root
• Capacity matrix must not be null or empty
• Capacity matrix must be square

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