Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Network Delay Time

LeetCode #743Medium
Dijkstra · finalize the nearest unfinished node

Given a directed weighted graph where each edge gives the travel time of a signal, and a starting node, return the time it takes for the signal to reach every node. If some node is unreachable, return -1.

Asked atAmazonGoogle
step 1 / 10
weighted directed graph
111
2
1
3
4
shortest dist from 2
nodedistdone
1∞
2∞
3∞
4∞
priority queue (min d)
(empty)
Dijkstra's algorithm
▸
1given graph, source
2dist[source] = 0, rest = ∞; pq = {(0, source)}
3while pq not empty:
4    (d, u) = pop min
5    if u already done: skip
6    mark u done
7    for (u → v, w):
8        if d + w < dist[v]: dist[v] = d+w; push
9answer = max(dist)   // −1 if any unreachable
state
  • source2
  • n4

line 1A signal starts at node 2 and travels along directed edges; each edge weight is the time to cross it. How long until EVERY node has the signal? That is the largest shortest-path distance from the source — a job for Dijkstra.