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 All-Routes Table.
One locally tempting edge can invalidate the whole journey.
How you win
- 1Recognize when Floyd-Warshall all-pairs shortest paths matches the clues
- 2Keep this true after every move: after phase k, dist[i][j] is shortest using only intermediates 0 through k
- 3Reach the result within O(V cubed)
Rules and pressure
- Target cost: O(V cubed)
- State rule: after phase k, dist[i][j] is shortest using only intermediates 0 through k
Lesson 1 of 3
Live algorithm trace
Floyd-Warshall all-pairs shortest paths
Complete execution1 of 6
0
k
1
2
Initialize direct routes and zero self-distances.
1
initialize diagonal zero and edge weights2
for k in vertices3
for i in vertices4
for j in vertices5
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])6
answer queriesmatrix = 0,3,10 / inf,0,1 / inf,inf,0
Truth to preserve / Cost target
Truth to preserve
after phase k, dist[i][j] is shortest using only intermediates 0 through k
Cost target
O(V cubed)
For each allowed intermediate k, compare every direct current route i-to-j with the route i-to-k-to-j. In-place updates are safe because all states in a phase may use intermediates only through k.
Your call · What should guide every step of this algorithm?