Back to course

Lesson 44: Handling Negative Weights: Introduction to Bellman-Ford

Algorithms: From Zero to Hero (A Beginner's Guide)

44. Handling Negative Weights: Introduction to Bellman-Ford

Dijkstra's algorithm fails if there are negative edge weights because its greedy assumption (that the minimum distance found so far is final) can be invalidated by a later path that includes a negative edge.

The Bellman-Ford Algorithm

Bellman-Ford solves the single-source shortest path problem even in graphs with negative weights.

Core Concept: Iterative Relaxation

Instead of greedily fixing paths, Bellman-Ford iteratively relaxes (updates) all edges in the graph V-1 times (where V is the number of vertices).

  1. Initialize distances (source=0, others=infinity).
  2. Repeat V-1 times:
    • For every edge (U, V) in the graph:
      • If dist[U] + weight(U, V) < dist[V], update dist[V].

Detecting Negative Cycles

If we run the relaxation step a V-th time and find that we can still relax (update) a distance, it means a negative cycle exists. Shortest paths are undefined in graphs reachable from a negative cycle.