[Verse 1]
Started with a graph, weighted and directed
Need the shortest paths, all pairs connected
Matrix D-I-J holds our distances tight
Initialize with edges, infinite for no sight
Direct connections get their weight assigned
All other pairs start undefined
This is the foundation, build it strong
Floyd-Warshall journey, come along
[Chorus]
K-I-J, that's the order we go
Through every vertex, let the magic flow
If D-I-K plus D-K-J is less than D-I-J
Update the distance, that's the Floyd way
All pairs shortest, no stone unturned
Three loops nested, knowledge earned
[Verse 2]
Outer loop K, that's our intermediate
Through every vertex, we mediate
Can we go from I to J through K instead
Check the sum, update what's in our head
If the detour's shorter than direct route
Replace the value, that's absolute
Relaxation step, optimization game
Floyd and Warshall, remember the name
[Chorus]
K-I-J, that's the order we go
Through every vertex, let the magic flow
If D-I-K plus D-K-J is less than D-I-J
Update the distance, that's the Floyd way
All pairs shortest, no stone unturned
Three loops nested, knowledge earned
[Bridge]
Time complexity, O of N cubed
Space complexity, N squared, that's the mood
Works with negative weights, but no negative cycles
Dynamic programming, breaking big problems to little
Bottom up approach, building solutions
Matrix transformation, evolution
[Verse 3]
After K iterations, we got the truth
All pairs shortest paths, that's the proof
From any vertex to any other node
Optimal distance, we cracked the code
Transitive closure, just change the rule
OR operation, Boolean tool
Floyd-Warshall flexes, adapts to need
Algorithmic power, guaranteed
[Chorus]
K-I-J, that's the order we go
Through every vertex, let the magic flow
If D-I-K plus D-K-J is less than D-I-J
Update the distance, that's the Floyd way
All pairs shortest, no stone unturned
Three loops nested, knowledge earned
[Outro]
N cubed time but the result's complete
All pairs shortest, can't be beat
Floyd-Warshall algorithm, now you know
Dynamic programming, watch it grow