Problem context and objectives
Mission briefing
Realm network architect · Routes have costs, dependencies, and unreliable bridges
Choose the next frontier that preserves the route guarantee: The Signal Delay.
One locally tempting edge can invalidate the whole journey.
How you win
- 1Recognize when Dijkstra network delay matches the clues
- 2Keep this true after every move: every popped nonstale distance is final because all edge weights are nonnegative
- 3Reach the result within O((V + E) log V)
Rules and pressure
- Target cost: O((V + E) log V)
- State rule: every popped nonstale distance is final because all edge weights are nonnegative
Lesson 1 of 3
Live algorithm trace
Dijkstra network delay
Complete execution1 of 6
1
2
source
3
4
Seed source node 2 with arrival zero.
1
dist[start] = 0; heap = [(0,start)]2
pop the smallest arrival3
skip a stale heap entry4
relax every outgoing edge5
push each improved distance6
return max distance or -1start = 2dist = [inf,0,inf,inf]heap = 0@2
Truth to preserve / Cost target
Truth to preserve
every popped nonstale distance is final because all edge weights are nonnegative
Cost target
O((V + E) log V)
Dijkstra settles nodes in nondecreasing arrival time. When all reachable nodes are settled, the largest settled distance is the time the final receiver gets the signal.
Your call · What should guide every step of this algorithm?