Network Delay Time
Understanding the Problem
This is a shortest path problem. The signal spreads from node k to all other nodes through the directed, weighted edges. A node receives the signal at the earliest possible time it can be reached, which is the length of the shortest path from k to that node.
The answer is the maximum over all those shortest distances. The signal travels along every path at once, so a node receives it as soon as the shortest path to it completes. For all n nodes to have the signal, we wait for the slowest one, which is the node whose shortest distance from k is largest. If any node cannot be reached, the answer is -1.
So the problem reduces to computing single-source shortest paths from node k, then returning the maximum distance. If any node has infinite distance, return -1.
Key Constraints:
0 <= w_i <= 100→ All edge weights are non-negative. This decides which algorithms are valid. Dijkstra requires non-negative weights, so it applies here. Negative weights would force Bellman-Ford.1 <= n <= 100→ With at most 100 nodes, an O(n^3) all-pairs algorithm runs in about a million operations, so even Floyd-Warshall is fast enough.1 <= times.length <= 6000→ Up to 6000 directed edges, with at most one edge per ordered pair. The graph is moderately dense for 100 nodes, but a single pass over the edge list is still cheap.
Approach 1: Bellman-Ford
Intuition
Bellman-Ford computes shortest paths by repeatedly relaxing every edge. Relaxing an edge (u, v, w) means: if going to u first and then taking this edge is shorter than the best known distance to v, record the smaller distance. One full pass relaxes all edges once. Bellman-Ford does V - 1 such passes.
V - 1 passes suffice because a shortest path in a graph with V nodes uses at most V - 1 edges. It never revisits a node, since revisiting would add a non-negative cycle and could not shorten the path. Each pass extends every shortest distance by at least one more correct edge along its path, so after V - 1 passes the longest shortest path has been fully resolved.
We initialize dist[k] = 0 for the source and infinity for every other node, then run the passes. Whatever distances remain are the shortest distances from k.
Algorithm
- Create a distance array of size
n + 1(nodes are 1-indexed), initialized to infinity. Setdist[k] = 0. - Repeat
n - 1times: - For each edge
(u, v, w)intimes, ifdist[u] + w < dist[v], updatedist[v] = dist[u] + w. - After all rounds, find the maximum value in
dist[1..n]. - If the maximum is infinity, return -1 (some node is unreachable). Otherwise, return the maximum.
Example Walkthrough
Code
- Time Complexity: O(V * E). We run V-1 rounds, and each round scans all E edges. With n up to 100 and edges up to 6000, this is at most 600,000 operations.
- Space Complexity: O(V). We store a distance array of size n+1.
Bellman-Ford scans all edges every round, even after distances stop changing. Because every edge weight here is non-negative, the next approach processes nodes in increasing order of distance and explores each node's edges only once.
Approach 2: Dijkstra's Algorithm (Min-Heap)
Intuition
Dijkstra's algorithm handles single-source shortest paths when all edge weights are non-negative, which holds here. It is greedy: among all nodes not yet finalized, the one with the smallest tentative distance already has its final shortest distance, so it can be settled and only its neighbors need to be explored. This avoids re-scanning every edge each round.
The signal spreads outward from node k, reaching the closest node first, then the next closest, and so on. A min-heap returns nodes in that order of distance. When a node is popped from the heap, its distance is final, and we relax its outgoing edges to push improved distances for its neighbors.
When a node u is popped with distance d, no later path to u can be shorter. Any other path to u must leave the settled set through some node still in the heap, whose distance is at least d, and then follow edges of non-negative weight. That path costs at least d, so d is final.
The d > dist[u] check handles lazy deletion. The code pushes a new entry instead of decreasing an existing key, so the heap can hold stale entries for a node whose distance was already improved. Those stale pops are skipped.
Algorithm
- Build an adjacency list from
times. - Create a distance array initialized to infinity. Set
dist[k] = 0. - Push
(0, k)into a min-heap (distance, node). - While the heap is not empty:
- Pop the node with the smallest distance. Call it
(d, u). - If
d > dist[u], skip (we already found a shorter path tou). - For each neighbor
(v, w)ofu, ifdist[u] + w < dist[v], updatedist[v]and push(dist[v], v)into the heap. - After the heap is empty, find the maximum distance in
dist[1..n]. - If the maximum is infinity, return -1. Otherwise, return it.
Example Walkthrough
Code
- Time Complexity: O(E log V). Each edge is relaxed at most once, and each relaxation involves a heap push (O(log V)). With E edges and V nodes, this gives O(E log V).
- Space Complexity: O(V + E). O(V) for the distance array, O(E) for the adjacency list, and O(V) for the heap in the worst case.
Approach 3: Floyd-Warshall (All-Pairs)
Intuition
Floyd-Warshall computes the shortest path between every pair of nodes, not just from the source. That is more than this problem asks for, but with n <= 100 the O(n^3) cost stays around a million operations, and the code is short and has no priority queue.
It builds shortest paths by allowing more intermediate nodes one at a time. Let dist[i][j] be the shortest distance from i to j using only intermediate nodes from a growing set. Start with the set empty, so dist[i][j] is the direct edge weight (or 0 when i == j, infinity otherwise). Then add node m to the allowed set. The shortest path from i to j either avoids m, leaving dist[i][j] unchanged, or routes through m, costing dist[i][m] + dist[m][j]. Taking the smaller of the two for every pair, after every node has been added as a permitted intermediate, dist[i][j] holds the true shortest distance.
The order of the loops matters. The intermediate node m must be the outermost loop. When m is being considered, dist[i][m] and dist[m][j] must already account for all earlier intermediates, which holds only if m is fixed while i and j sweep inside it.
Once the matrix is filled, the answer is the maximum entry in row k. If any entry in that row is still infinity, node k cannot reach that node, so return -1.
Algorithm
- Create an
(n + 1) x (n + 1)matrixdist, initialized to infinity. Setdist[i][i] = 0for every node. - For each edge
(u, v, w), setdist[u][v]to the minimum of its current value andw. Taking the minimum matters because the input can contain parallel edges between the same pair, and only the cheapest one should survive. - For each intermediate node
mfrom 1 to n (outermost loop), for eachi, for eachj: ifdist[i][m] + dist[m][j] < dist[i][j], updatedist[i][j]. Skip pairs wheredist[i][m]ordist[m][j]is infinity to avoid overflow. - Scan row
k. If anydist[k][j]is infinity, return -1. Otherwise return the maximum value in the row.
Example Walkthrough
Code
- Time Complexity: O(V^3). Three nested loops over all nodes. With n up to 100, this is about one million operations.
- Space Complexity: O(V^2). The distance matrix holds an entry for every pair of nodes.
For this problem, Dijkstra is the best fit: O(E log V) beats Floyd-Warshall's O(V^3) and uses O(V + E) space instead of O(V^2). Floyd-Warshall stays competitive only because n is capped at 100, and it is the approach to pick when the shortest distance between every pair of nodes is needed, not just from one source. Bellman-Ford is the choice when edge weights can be negative.