Log In Sign Up
Day 47

Day 47: Bellman-Ford Algorithm

47/60 Days

Day 47: Bellman-Ford Algorithm #

Welcome to Day 47 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore the Bellman-Ford algorithm, a versatile algorithm for finding the shortest paths from a single source vertex to all other vertices in a weighted graph.

What is the Bellman-Ford Algorithm? #

The Bellman-Ford algorithm is used to find the shortest paths from a source vertex to all other vertices in a weighted graph. Unlike Dijkstra’s algorithm, Bellman-Ford can handle graphs with negative edge weights and can detect negative cycles in the graph.

How Does It Work? #

The algorithm works by repeatedly relaxing all edges V-1 times, where V is the number of vertices in the graph. After this process, it checks for negative-weight cycles.

  1. Initialize distances from the source to all vertices as infinite and distance to the source itself as 0.
  2. Relax all edges |V| - 1 times. For each edge (u, v) with weight w, if dist[v] > dist[u] + w, then update dist[v] = dist[u] + w.
  3. Check for negative-weight cycles. For each edge (u, v) with weight w, if dist[v] > dist[u] + w, then there is a negative-weight cycle.

Implementing Bellman-Ford …