Network Delay Time

NeetCode: Network Delay Time · LeetCode: 743. Network Delay Time · Difficulty: Medium

You are given a directed weighted graph of n nodes labelled 1..n and a list of times as [u, v, w] (a signal travels from u to v in w time). A signal is sent from node k. Return the time it takes for all nodes to receive it, or -1 if some node is unreachable.

Example

Text

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

The answer is the largest shortest-path distance from k to any node, so this is a single-source shortest path problem with non-negative weights.

Brute force: Bellman-Ford

Start with dist[k] = 0 and everything else infinite. Then repeat: for every edge u -> v with weight w, if dist[u] + w < dist[v], improve dist[v]. A shortest path has at most n - 1 edges, so n - 1 full passes are enough; the loop stops early when a pass changes nothing.

Distances are long and the infinity marker is Long.MAX_VALUE. The code skips edges whose source is still infinite, because Long.MAX_VALUE + w would wrap to a negative number.

Java

import java.util.Arrays;

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        final long INF = Long.MAX_VALUE;
        long[] dist = new long[n + 1];
        Arrays.fill(dist, INF);
        dist[k] = 0;
        for (int pass = 1; pass < n; pass++) {
            boolean changed = false;
            for (int[] t : times) {
                int u = t[0], v = t[1], w = t[2];
                if (dist[u] != INF && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    changed = true;
                }
            }
            if (!changed) break;
        }
        long worst = 0;
        for (int i = 1; i <= n; i++) worst = Math.max(worst, dist[i]);
        return worst == INF ? -1 : (int) worst;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.networkDelayTime(new int[][] {{2, 1, 1}, {2, 3, 1}, {3, 4, 1}}, 4, 2));
        System.out.println(s.networkDelayTime(new int[][] {{1, 2, 1}}, 2, 1));
        System.out.println(s.networkDelayTime(new int[][] {{1, 2, 1}}, 2, 2));
        System.out.println(s.networkDelayTime(new int[0][], 1, 1));
    }
}

Output

Bellman-Ford tolerates negative weights, which this problem does not need, and pays for it by re-scanning every edge in each pass. Time: O(V * E). Space: O(V).

Optimal: Dijkstra with a min-heap

With non-negative weights, the unvisited node with the smallest tentative distance is already final: any other route to it would have to pass through a node at least as far away. So repeatedly pop the closest node from a min-heap, and relax its outgoing edges.

Java's PriorityQueue is a min-heap, so the smallest entry comes out first. Each entry is a long[]{distance, node} and the comparator is Long.compare on the distance (subtracting the two values could overflow). Stale heap entries (a node already settled with a smaller distance) are skipped.

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
        for (int[] t : times) graph.get(t[0]).add(new int[] {t[1], t[2]});

        long[] dist = new long[n + 1];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[k] = 0;
        PriorityQueue<long[]> heap = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
        heap.add(new long[] {0, k});
        while (!heap.isEmpty()) {
            long[] top = heap.poll();
            long d = top[0];
            int u = (int) top[1];
            if (d > dist[u]) continue; // stale entry
            for (int[] edge : graph.get(u)) {
                int v = edge[0];
                long w = edge[1];
                if (d + w < dist[v]) {
                    dist[v] = d + w;
                    heap.add(new long[] {dist[v], v});
                }
            }
        }
        long worst = 0;
        for (int i = 1; i <= n; i++) worst = Math.max(worst, dist[i]);
        return worst == Long.MAX_VALUE ? -1 : (int) worst;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.networkDelayTime(new int[][] {{2, 1, 1}, {2, 3, 1}, {3, 4, 1}}, 4, 2));
        System.out.println(s.networkDelayTime(new int[][] {{1, 2, 1}}, 2, 1));
        System.out.println(s.networkDelayTime(new int[][] {{1, 2, 1}}, 2, 2));
        System.out.println(s.networkDelayTime(new int[0][], 1, 1));
    }
}

Output

Time: O((V + E) log V) (each edge can push at most one heap entry). Space: O(V + E).