[Verse 1]
Graph theory nightmare, distances unknown
Negative weights lurking, shortest paths overthrown
Dijkstra falls apart when edges bite back
Time for Bellman-Ford to pick up the slack
Initialize all vertices to infinity's throne
Except your source vertex, set that to zone zero
Now we iterate, that's the magic number
V minus one times, don't let your mind slumber
[Chorus]
Relax every edge, V minus one rounds
Check each connection, let distances unwound
If source to U plus weight UV
Beats current distance to V, then modify
Bellman-Ford detects what others cannot see
Negative cycles hiding in your tree
V minus one rounds, then one final check
Negative cycles? Time to genuflect
[Verse 2]
Edge relaxation, that's the beating heart
Compare the detour to your current chart
Distance to source plus the edge's cost
If it's smaller, update what you've lost
Each iteration guarantees precision
One more shortest path reaches completion
But negative cycles break the game
Infinite decrease, distances inflame
[Chorus]
Relax every edge, V minus one rounds
Check each connection, let distances unwound
If source to U plus weight UV
Beats current distance to V, then modify
Bellman-Ford detects what others cannot see
Negative cycles hiding in your tree
V minus one rounds, then one final check
Negative cycles? Time to genuflect
[Bridge]
Final verification round arrives
If any distance still derives
A better path than what you hold
Negative cycle story's told
Return false, the graph is poisoned
Shortest paths cannot be reasoned
[Outro]
O of V times E complexity cost
But negative cycles won't leave you lost
Bellman-Ford succeeds where others stumble
When weighted graphs make algorithms crumble