[Verse 1]
Started with a graph, nodes connected tight
Direct paths showing, but the picture ain't right
Need to find the shortest between every pair
Floyd got the vision, Warshall made it clear
Three nested loops, that's the algorithm way
K in the middle, that's how we gonna play
Check every vertex as an intermediate stop
Compare the distances, see which route's on top
[Chorus]
All pairs shortest path, that's what we calculate
Dynamic programming, seal every node's fate
K-I-J, remember the order straight
If distance through K makes the journey lightweight
Update the matrix, iteration by state
Floyd-Warshall running, no path comes too late
All pairs shortest path, algorithms so great
N-cubed complexity, but results first-rate
[Verse 2]
Initialize the matrix, direct edges in place
Infinity symbol for paths with no trace
Diagonal zeros, node to itself is free
Now we iterate through K from one to N-D
For every I and J, we check the condition
Is I-K plus K-J a better transmission?
If the sum is smaller than the current cost
Update that entry, optimization's not lost
[Chorus]
All pairs shortest path, that's what we calculate
Dynamic programming, seal every node's fate
K-I-J, remember the order straight
If distance through K makes the journey lightweight
Update the matrix, iteration by state
Floyd-Warshall running, no path comes too late
All pairs shortest path, algorithms so great
N-cubed complexity, but results first-rate
[Bridge]
Works with negative edges, but no negative cycles
Detects them too when diagonal's not idle
Transitive closure, reachability check
Boolean matrix, giving mad respect
From routing protocols to network design
Finding bottlenecks, keeping data in line
[Verse 3]
After N iterations, the matrix complete
Every shortest path, the algorithm's feat
Dense graphs benefit, sparse might want Dijkstra
But Floyd-Warshall's clean, no priority extra
Simple three-line core in the nested loop heart
Check, compare, update - that's the algorithmic art
Bottom-up approach, subproblems combine
Optimal substructure, the DP design
[Chorus]
All pairs shortest path, that's what we calculate
Dynamic programming, seal every node's fate
K-I-J, remember the order straight
If distance through K makes the journey lightweight
Update the matrix, iteration by state
Floyd-Warshall running, no path comes too late
All pairs shortest path, algorithms so great
N-cubed complexity, but results first-rate
[Outro]
Floyd-Warshall master, shortest paths we trace
Every pair connected in algorithmic space
From graph theory classic to real-world application
Dynamic programming's finest demonstration