LeetCode Study Note | Problem 743: Network Delay Time

📘 Problem Overview

You are given a directed, weighted graph with n nodes (1-indexed), and a list of travel times times, where each element is [u, v, w], representing a signal from node u to node v taking w time.

You are also given a starting node k. Your task is to compute how long it takes for all nodes to receive the signal.

If it’s impossible to reach all nodes, return -1.

🧠 Core Algorithm: Dijkstra

Dijkstra is a single-source shortest path algorithm for graphs with non-negative edge weights.

It finds the minimum distance from the source node to all other nodes.

🧭 General Dijkstra Steps

1. Initialize a dist[] array: dist[source] = 0, all others = INF.

2. Initialize a visited[] array: tracks nodes whose shortest path has been finalized.

3. Repeat n times:

   • Select the unvisited node with the smallest dist[].

   • Mark it visited.

   • Update its neighbors’ distances (relax edges).

4. Return the maximum value in dist[].

🧠 Method 1: Naive Dijkstra (Adjacency Matrix + Linear Search)

✅ Suitable for: Small graphs (n ≤ 100)

public int networkDelayTime(int[][] times, int n, int k) {
    final int INF = Integer.MAX_VALUE / 2;
    int[][] graph = new int[n][n];
    for (int[] row : graph) Arrays.fill(row, INF);
    for (int[] t : times) graph[t[0] - 1][t[1] - 1] = t[2];

    int[] dist = new int[n];
    Arrays.fill(dist, INF);
    dist[k - 1] = 0;

    boolean[] visited = new boolean[n];

    for (int i = 0; i < n; i++) {
        int curr = -1;
        for (int j = 0; j < n; j++) {
            if (!visited[j] && (curr == -1 || dist[j] < dist[curr])) {
                curr = j;
            }
        }

        if (dist[curr] == INF) break;

        visited[curr] = true;
        for (int j = 0; j < n; j++) {
            dist[j] = Math.min(dist[j], dist[curr] + graph[curr][j]);
        }
    }

    int max = Arrays.stream(dist).max().getAsInt();
    return max == INF ? -1 : max;
}

⚡ Method 2: Dijkstra with Min-Heap (Adjacency List + PriorityQueue)

✅ Suitable for: Large graphs, sparse graphs, interviews

public int networkDelayTime(int[][] times, int n, int k) {
    Map<Integer, List<int[]>> graph = new HashMap<>();
    for (int[] t : times) {
        graph.computeIfAbsent(t[0], x -> new ArrayList<>()).add(new int[]{t[1], t[2]});
    }

    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[k] = 0;

    PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    heap.offer(new int[]{0, k});

    boolean[] visited = new boolean[n + 1];

    while (!heap.isEmpty()) {
        int[] curr = heap.poll();
        int time = curr[0], node = curr[1];

        if (visited[node]) continue;
        visited[node] = true;

        if (!graph.containsKey(node)) continue;
        for (int[] edge : graph.get(node)) {
            int neighbor = edge[0], weight = edge[1];
            if (dist[neighbor] > time + weight) {
                dist[neighbor] = time + weight;
                heap.offer(new int[]{dist[neighbor], neighbor});
            }
        }
    }

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

🆚 Comparison: Naive vs Heap-Optimized Dijkstra

🧃 Final Tips

• Dijkstra only works with non-negative edge weights. For graphs with negative edges, use Bellman-Ford.

• The heap version is preferred in interviews and real-world applications.

• Common combo: dist[] + visited[] + heap = the ultimate Dijkstra toolkit.

• Be comfortable with both matrix-based and map-based graph representations.