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 Negative Loop.
One locally tempting edge can invalidate the whole journey.
How you win
- 1Recognize when Bellman-Ford cycle detection matches the clues
- 2Keep this true after every move: after r rounds, distances cover every source path using at most r edges
- 3Reach the result within O(VE)
Rules and pressure
- Target cost: O(VE)
- State rule: after r rounds, distances cover every source path using at most r edges
Lesson 1 of 3
Live algorithm trace
Bellman-Ford cycle detection
Complete execution1 of 5
0-1:1
edge
1-2:-2
2-1:-2
Initialize source 0 before any relaxation.
1
dist[src] = 02
relax all edges n - 1 times3
stop early if no update4
scan every edge once more5
if any reachable edge improves: return true6
return falsesource = 0dist = [0,inf,inf]
Truth to preserve / Cost target
Truth to preserve
after r rounds, distances cover every source path using at most r edges
Cost target
O(VE)
Any simple path has at most n minus one edges. If a reachable distance can still improve on one extra relaxation pass, the improvement must depend on a reachable negative-weight cycle.
Your call · What should guide every step of this algorithm?