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 Bounded Flights.
One locally tempting edge can invalidate the whole journey.
How you win
- 1Recognize when Edge-bounded Bellman-Ford matches the clues
- 2Keep this true after every move: after round r, dist[v] is the cheapest route using at most r edges
- 3Reach the result within O((k + 1)E)
Rules and pressure
- Target cost: O((k + 1)E)
- State rule: after round r, dist[v] is the cheapest route using at most r edges
Lesson 1 of 3
Live algorithm trace
Edge-bounded Bellman-Ford
Complete execution1 of 6
0
source
1
2
Before any flight, only city 0 has finite cost.
1
dist[src] = 02
repeat k + 1 rounds3
next = copy(dist)4
for every flight5
next[to] = min(next[to], dist[from] + price)6
dist = next7
return destination or -1src = 0dst = 2k = 1dist = [0,inf,inf]
Truth to preserve / Cost target
Truth to preserve
after round r, dist[v] is the cheapest route using at most r edges
Cost target
O((k + 1)E)
One copied relaxation round permits one additional edge. Reading only the previous round prevents a newly improved city from chaining multiple flights inside the same edge budget.
Your call · What should guide every step of this algorithm?