[Verse 1]
Graph vertices connected by weighted edges
Shortest paths hide beneath mathematical pledges
Brute force fails when networks grow massive
Floyd-Warshall swoops in, elegant and passive
Dynamic programming breaks the complex maze
Three nested loops in polynomial days
Distance matrix holds every possible route
From every node to every substitute
[Chorus]
Floyd-Warshall, three loops deep
K-I-J, the pattern we keep
If K makes the distance smaller
Update that matrix, distance crawler
Floyd-Warshall, O-N-cubed time
Shortest paths in every rhyme
[Verse 2]
Initialize distances, infinity's the start
Direct edges get their weights, that's the art
Diagonal zeros, node to itself is free
Now the algorithm works its sorcery
Outer loop K, the intermediate guide
Middle vertex that might provide
A cheaper route from I to J
Check if K shortens the way
[Chorus]
Floyd-Warshall, three loops deep
K-I-J, the pattern we keep
If K makes the distance smaller
Update that matrix, distance crawler
Floyd-Warshall, O-N-cubed time
Shortest paths in every rhyme
[Bridge]
All pairs shortest paths computed clean
No source node required in this machine
Negative edges? No problem here
Unless negative cycles appear
Matrix converges after N rounds
Transitive closure can be found
[Verse 3]
Distance I-J through intermediate K
Compare with direct I-J way
Minimum function decides the fate
Which path has the lighter weight
Building solutions from subproblems solved
Bottom-up approach gets problems resolved
When the triple loop finally ends
Every shortest path transcends
[Chorus]
Floyd-Warshall, three loops deep
K-I-J, the pattern we keep
If K makes the distance smaller
Update that matrix, distance crawler
Floyd-Warshall, O-N-cubed time
Shortest paths in every rhyme
[Outro]
From dense graphs to sparse connections
Floyd-Warshall maps all directions
Cubic complexity, polynomial grace
All-pairs shortest paths embrace