Network Delay Time: the idea to remember.

The core insight

Initialize source distance to zero and repeatedly relax every directed edge.

Why it works

After enough passes, every shortest simple path has been considered; the latest finite arrival determines the total delay.

The mistake to avoid

Check reachability before adding an edge weight; an unreachable node makes the final answer minus one.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// Initialize source distance to zero and repeatedly relax every directed edge.
public int networkDelayTime(int[][] times, int n, int k) {

    int[] paths = new int[n];
    Arrays.fill(paths, Integer.MAX_VALUE);

    paths[k - 1] = 0;

    for (int i = 0; i < n; i++) {

        int[] temp = new int[n];
        temp = Arrays.copyOf(paths, paths.length);


        for (int j = 0; j < times.length; j++) {
            int src = times[j][0]; 
            int tgt = times[j][1]; 
            int time = times[j][2]; 

            if (
                temp[src - 1] != Integer.MAX_VALUE &&
                temp[src - 1] + time < temp[tgt - 1]
            ) {
                temp[tgt - 1] = temp[src - 1] + time;
            }
        }


        paths = temp;
    }

    int result = Integer.MIN_VALUE;


    for (int i = 0; i < n; i++) {
        if (paths[i] == Integer.MAX_VALUE) {
            return -1;
        }
        result = Math.max(result, paths[i]);
    }


    return result;
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection