← Back to DSA Animator
Network Delay Time LC #743 Medium Graph · Dijkstra
Problem

You are given a network of n nodes labeled 1 to n. You are also given times, a list of travel times as directed edges times[i] = (u, v, w) where u is the source, v is the target, and w is the time. We send a signal from node k. Return the minimum time for all n nodes to receive the signal. If impossible, return -1.

Example 1
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Explanation: Node 2 sends to 1 and 3 at t=1; node 3 sends to 4 at t=2. Max dist = 2.
Example 2
Input: times = [[1,2,1]], n = 2, k = 1
Output: 1
Example 3
Input: times = [[1,2,1]], n = 2, k = 2
Output: -1
Explanation: Node 1 unreachable from node 2.
Constraints: 1 ≤ k ≤ n ≤ 100  |  1 ≤ times.length ≤ 6000  |  All (ui, vi) pairs are distinct
Try Examples
Custom: edges (u-v-w) / n / k
Approach
Dijkstra's Algorithm
Min-heap: process shortest-dist node. Relax neighbors. dist[k]=0. Answer = max(dist).
Graph & dist[]
Load an example.
Variables
u (process)
—
dist[u]
—
Relax v→
—
max
—
Step Logic
Press ▶ Play or Next Step.
✓
Ready
0/0
Select example and Play.
Algorithm
1
dist[k]=0, others=∞
2
Pop min; relax neighbors
3
Return max(dist) or -1
Time
O((V+E)log V)
Space
O(V)
Why Dijkstra

Greedy: always process closest unvisited node. Relaxation: if dist[u]+w<dist[v], update. Max dist = time for last node to receive signal.