Network Delay Time
MediumDijkstra, then take the farthest arrival
Problem
Return the time for a signal from a source to reach all nodes, or -1 if some are unreachable.
Run Dijkstra from the source; the answer is the largest shortest-distance (or -1 if some node is cut off).
The idea
A signal reaches each node at that node's shortest travel time, so run Dijkstra from the source k. Once every node is settled, the network is fully lit only when the last node hears it — that is the largest of the shortest times. If any node is still ∞ (unreachable), return -1.
Step 1 of 13. Goal: the shortest distance from A to every other node. Start A = 0, everyone else = ∞ (unknown). dist [0, ∞, ∞, ∞, ∞], settled —.
1dist[k] = 0, all others = ∞2min-heap H = {(0, k)}3while H not empty:4 (d, u) = pop-smallest from H5 for each edge (u → v, weight w):6 if d + w < dist[v]:7 dist[v] = d + w; push (dist[v], v)8return max(dist) // -1 if any node stayed ∞Input
- nodes
- 5, 6 edges
Memory
- dist
- [0, ∞, ∞, ∞, ∞]
- frontier
- —
Output
- settled
- —
- shortest dist
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
- Output:
- 2
- Explanation:
- The signal reaches the farthest node in 2.
Example 2
- Input:
- times = [[1,2,1]], n = 2, k = 1
- Output:
- 1
- Explanation:
- One hop of cost 1.
Example 3
- Input:
- times = [[1,2,1]], n = 2, k = 2
- Output:
- -1
- Explanation:
- Node 1 is unreachable from 2 → -1.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.