Network Delay Time

Given n network nodes and edges (u,v,w), find the time for all nodes to receive signal sent from node k. Return -1 if not all nodes can receive the signal.

Example 1

Input: times=[[2,1,1],[2,3,1],[3,4,1]], n=4, k=2 → Output: 2

Example 2

Input: times=[[1,2,1]], n=2, k=1 → Output: 1

Solution Approach

Dijkstra from node k. The answer is the maximum shortest distance among all reachable nodes.

Build adjacency list. Run Dijkstra from k.
dist[] tracks shortest time to each node.
After Dijkstra, find max(dist[]). If any node is unreachable (INF), return -1.

Java

import java.util.*;

class Solution {
    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[]> pq = new PriorityQueue<>((a,b)->a[1]-b[1]);
        pq.offer(new int[]{k,0});
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            if (cur[1] > dist[cur[0]]) continue;
            for (int[] nb : graph.getOrDefault(cur[0], Collections.emptyList())) {
                int newDist = dist[cur[0]] + nb[1];
                if (newDist < dist[nb[0]]) { dist[nb[0]] = newDist; pq.offer(new int[]{nb[0],newDist}); }
            }
        }
        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;
    }
}

Time Complexity: O((V+E) log V)
Space Complexity: O(V+E)