[Verse 1] Started with a weighted graph, edges pointing everywhere Some weights are negative, that's the challenge we prepare Initialize distances, set source node to zero Every other vertex marked infinity, that's our hero V minus one iterations, that's the magic number Relaxation process, watch the distances go under Check each edge systematically, update if we find A shorter path exists, blow your algorithmic mind [Chorus] Relax all edges, V minus one times Detect negative cycles, that's how the algorithm climbs Distance array updating, shorter paths we find Bellman-Ford's got your back when Dijkstra's left behind V minus one, V minus one, remember that phrase Negative cycles caught, in algorithmic ways [Verse 2] Take an edge from U to V, weight between them known If distance U plus weight is less than V alone Update that distance, mark it as the new best route Relaxation in action, that's what we're about Do this for every edge, in every iteration Building shortest paths across the whole graph nation Time complexity's bigger, O of V times E But handling negatives is the key to victory [Chorus] Relax all edges, V minus one times Detect negative cycles, that's how the algorithm climbs Distance array updating, shorter paths we find Bellman-Ford's got your back when Dijkstra's left behind V minus one, V minus one, remember that phrase Negative cycles caught, in algorithmic ways [Bridge] After V minus one rounds, we ain't done yet One more pass through edges, place your final bet If any distance changes, negative cycle's there Return false to the caller, handle with care Dynamic programming essence, optimal substructure Building solutions bottom-up, that's the algorithm's nature [Verse 3] Applications everywhere, network routing protocols Currency arbitrage detection, breaking financial walls Distributed systems use it, when networks can fail Negative edge weights modeling, telling the real tale Slower than Dijkstra, but it gets the job complete When negative weights appear, Bellman-Ford can't be beat From Bellman and Ford, their names live in the code Shortest path with negatives, that's their lasting ode [Outro] V minus one iterations, relax every edge you see Detect those cycles, set your graph theory free Bellman-Ford algorithm, handling what others can't do Negative weights in your graph, this algorithm's for you
← Implementation and Time Complexity | Floyd-Warshall algorithm →