Bellman-Ford Algorithm

@bellmanford_algorithm

The Bellman-Ford algorithm finds the shortest path from a source node to all other nodes, even when there are negative edge weights. It works by repeatedly improving distance estimates.

Pseudo-code
function bellman_ford(graph, source):

  # Step 1: Initialize distances
  for each vertex v in graph:
    dist[v] = INF
    prev[v] = null

  dist[source] = 0

  # Step 2: Relax all edges V-1 times
  for i from 1 to V-1:
    for each edge (v, w) with weight weight(v, w):

      # Relaxation step
      if dist[v] + weight(v, w) < dist[w]:
        dist[w] = dist[v] + weight(v, w)
        prev[w] = v

  # Step 3: Check for negative cycles
  for each edge (v, w):
    if dist[v] + weight(v, w) < dist[w]:
      return 'Graph contains negative cycle'

  return dist, prev
  • dist A distance table where dist[v] stores the shortest known distance from the source to vertex v.
  • prev Stores the previous vertex in the shortest path (used to rebuild the path).
  • i Loop counter used to repeat the relaxation process multiple times.
  • v The current vertex being processed.
  • w A neighbor vertex connected to v via an edge.
  • INF A very large value representing infinity (initial unknown distances).
  • V The number of vertices in the graph.
  • E The number of edges in the graph.
Recipe Steps
1

Start with guesses — Assume every location is infinitely far away, except your starting point which is 0.

2

Try every road — For each road, check if going through it gives you a shorter path.

3

If you find a shorter path, update your distance. This is like correcting your route.

4

Repeat this process many times (V-1 times) so all paths get fully improved.

5

Final check — If you can still improve distances, it means there is a negative cycle (a loop that keeps reducing distance forever).

Questions & Answers

It can handle negative weights, while Dijkstra cannot.

It is updating a distance if a shorter path is found.

Because the longest possible shortest path has at most V-1 edges.

There is a negative cycle in the graph.
- Time complexity is O(V * E), slower than Dijkstra.
- Works with negative edge weights, which is its big advantage.
- Tip: Think of it as repeatedly improving guesses until they are correct.
- Common mistake: Forgetting the negative cycle check step.
- Useful in problems where edge weights can be negative.

Related Algorithms
Dijkstra's Algorithm

Dijkstra's Algorithm finds the shortest path from one starting node to all other nodes in a graph by always expanding the currently closest node first.

View
Floyd-Warshall Algorithm

The Floyd-Warshall algorithm finds the shortest paths between all pairs of nodes by gradually improving paths using intermediate nodes.

View