The example problem
Junctions 1 to n are connected by one-way roads with travel times (times[i] = (u, v, w)). A signal starts at junction k. Return how long until every junction has received it (the largest of the fastest times), or −1 if some junction can never be reached.
Input: times = [[1,2,4], [1,3,1], [3,2,2], [2,4,1], [3,4,5], [4,5,3]], n = 5, k = 1 Output: 7 (junction 5 is last: 1 → 3 → 2 → 4 → 5)
Picture it
Picture a city map: pins are junctions, roads are labelled with minutes. Each pin shows its best known time (∞ at first). We always “lock in” the unfinished pin with the smallest time, because no route through farther pins could beat it. From that pin we check each road: if going through it is faster, update the neighbour’s time.
The key idea
Dijkstra: a min-heap of (time, junction); pop the closest, relax its roads. Works when no road has negative time.
Python
def network_delay_time(times, n, k):
roads = defaultdict(list)
for u, v, w in times: # one-way
roads[u].append((v, w))
dist = {k: 0}
pq = [(0, k)]
while pq:
d, u = heappop(pq) # closest
if d > dist[u]:
continue
for v, w in roads[u]:
if d + w < dist.get(v, inf):
dist[v] = d + w
heappush(pq, (dist[v], v))
if len(dist) < n:
return -1 # someone never hears
return max(dist.values())Practise graphs
NeetCode 150 problems that use it
Graphs · Advanced Graphs ·
- LeetCode 200 · MediumNumber of IslandsPainting islands on a sea chart
- LeetCode 133 · MediumClone GraphPhotocopying a city map junction by junction
- LeetCode 695 · MediumMax Area of IslandMeasuring the biggest island
- LeetCode 417 · MediumPacific Atlantic Water FlowRain on an island draining to two oceans
- LeetCode 130 · MediumSurrounded RegionsCapturing surrounded stones on a Go board
- LeetCode 994 · MediumRotting OrangesRot spreading through a fruit crate
- LeetCode 286 · MediumWalls and GatesDistance from every room to the nearest exit
- LeetCode 207 · MediumCourse ScheduleCan every course be taken?
- LeetCode 210 · MediumCourse Schedule IIA timetable that respects every prerequisite
- LeetCode 684 · MediumRedundant ConnectionThe one cable too many
- LeetCode 323 · MediumNumber of Connected Components in an Undirected GraphCounting circles of friends
- LeetCode 261 · MediumGraph Valid TreeIs this network a tree?
- LeetCode 127 · HardWord LadderChanging one letter at a time
- LeetCode 332 · HardReconstruct ItineraryUsing every plane ticket exactly once
- LeetCode 1584 · MediumMin Cost to Connect All PointsLaying the cheapest cables between houses
- LeetCode 743 · MediumDijkstraFastest route across the city
- LeetCode 778 · HardSwim in Rising WaterWaiting for the flood to let you swim across
- LeetCode 269 · HardAlien DictionaryWorking out an alien alphabet from a sorted word list
- LeetCode 787 · MediumCheapest Flights Within K StopsThe cheapest trip with a limited number of layovers