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 Cheapest Route.
One locally tempting edge can invalidate the whole journey.
How you win
- 1Recognize when Dijkstra shortest path matches the clues
- 2Keep this true after every move: every settled node has its final shortest distance
- 3Reach the result within O((V + E) log V)
Rules and pressure
- Target cost: O((V + E) log V)
- State rule: every settled node has its final shortest distance
Lesson 1 of 3
Live algorithm trace
Dijkstra shortest path
Complete execution1 of 7
0
current
1
2
Only the start node has a known distance, zero.
1
dist[start] = 02
pop smallest distance3
relax outgoing edges4
return dist[end]start = 0end = 1dist = [0, ∞, ∞]heap = [(0, 0)]
Truth to preserve / Cost target
Truth to preserve
every settled node has its final shortest distance
Cost target
O((V + E) log V)
Dijkstra always expands the unsettled node with the smallest known distance. Nonnegative edges guarantee that this distance can no longer improve.
Your call · What should guide every step of this algorithm?