DSA problem
Network Delay Time
You are given a network of n nodes labeled from 1 to n and a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from u to v. You are also given a starting node k. Return the minimum time it takes for all the n nodes to receive the signal, or -1 if it is impossible.
This is a classic single-source shortest-path problem on a weighted directed graph with non-negative edge weights. Since every node must eventually receive the signal, the answer is the maximum of the shortest distances from k to every other node. If any node is unreachable, no finite time satisfies "all nodes receive", so the answer is -1.
A brute-force Bellman-Ford solution would relax all edges n - 1 times, giving O(n * E) time. That works but is slower than necessary because edge weights here are non-negative.
The optimal algorithm is Dijkstra's with a min-heap. Push the source with distance 0, then repeatedly pop the closest unsettled node and relax its outgoing edges. Each node settles exactly once, and each edge is relaxed at most once, yielding O((n + E) log n) time. After the heap empties, scan the distance array: if every entry is finite return the maximum, otherwise return -1.
Examples
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 22times = [[1,2,1]], n = 2, k = 11times = [[1,2,1]], n = 2, k = 2-1Constraints
- 1 <= k <= n <= 100
- 1 <= times.length <= 6000
- times[i].length == 3
- 1 <= ui, vi <= n
- ui != vi
- 0 <= wi <= 100
- All the pairs (ui, vi) are unique. (i.e., no multiple edges.)
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.