Problem 26.1 · Shortest PathsMedium

Network Delay Time

What it teaches: Plain Dijkstra: the answer is the largest shortest distance.

Practise it on judges as “Network Delay Time”.

The problem

times[i] = [u, v, w] means a signal takes w time from node u to node v (directed). Send a signal from node k. Return the time for all n nodes to receive it, or −1 if some never do.

Example 1

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

Constraints

1 ≤ n ≤ 100
0 ≤ w ≤ 100

Pattern clues in the wording

→ Weighted directed graph
→ Time for everything to be reached = max of shortest distances

These clues point to Dijkstra's Shortest Path: Always expand the closest unfinished node from a min-heap; with non-negative weights, its distance is final.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        return -1;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	times = [[2,1,1],[2,3,1],[3,4,1]] n = 4 k = 2	2
2	times = [[1,2,1]] n = 2 k = 1	1
3	times = [[1,2,1]] n = 2 k = 2	-1

From slow to fast

Approaches

1. Dijkstra · O(E log V)

Dijkstra

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

Adjacency list of (v, w); heap of (dist, node); skip stale entries.

Approach 1

import java.util.*;

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
        for (int[] t : times) adj.get(t[0]).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) -> Integer.compare(a[0], b[0]));
        pq.offer(new int[]{0, k});
        while (!pq.isEmpty()) {
            int[] top = pq.poll();
            int d = top[0], u = top[1];
            if (d > dist[u]) continue;
            for (int[] e : adj.get(u)) {
                if (d + e[1] < dist[e[0]]) { dist[e[0]] = d + e[1]; pq.offer(new int[]{dist[e[0]], e[0]}); }
            }
        }
        int best = 0;
        for (int v = 1; v <= n; v++) {
            if (dist[v] == Integer.MAX_VALUE) return -1;
            best = Math.max(best, dist[v]);
        }
        return best;
    }
}

Verdict: The textbook use.

Before you submit

Edge cases and common mistakes

Test these inputs

Unreachable node
n = 1

Mistakes people make

Using BFS levels (ignores weights).

Interview

Follow-up questions

When would Bellman-Ford be better here?

Command Palette

The problem

Approaches

Dijkstra

Edge cases and common mistakes

Follow-up questions