Bellman-Ford Algorithm

Say you are booking a trip. You start from one city. You want the cheapest way to reach every other city. Some routes even pay you back, like a cashback offer. So the cost on that step is negative. The popular shortest-path algorithm, Dijkstra, breaks here. It assumes no route ever pays you back. So when costs can go negative, we need a different tool. That tool is the Bellman-Ford algorithm.

📚 What Is Bellman-Ford?

Bellman-Ford finds the shortest path from one starting vertex to every other vertex in a weighted graph. A shortest path here means the path with the smallest total weight. It is not about the fewest hops.

The thing that makes it special:

• It works even when some edges have negative weights. A negative weight just means that step lowers your total cost.
• It can tell you when the graph has a negative cycle. A negative cycle is a loop you can go around again and again, lowering your cost with no end. When that happens, no real shortest path exists.

Dijkstra cannot do either of those. Bellman-Ford is slower, but it gives correct answers on graphs Dijkstra cannot handle.

🌍 A Real-World Way to Picture It

Think of currency exchange. You have rupees and you want dollars. There are many ways to convert. You can go rupees to euros to dollars. Or you can go rupees straight to dollars. Each hop has a cost. Some hops, because of a good rate, leave you with more value. That is a negative cost.

Now imagine a loop. You convert rupees to euros, then to pounds, then back to rupees. And you end up with more money than you started with. You could go around that loop forever and keep gaining value with no end. That broken loop is a negative cycle. Bellman-Ford spots this and says “stop, there is no sane answer here.”

🎯 The Core Idea: Relaxation

The whole algorithm rests on one small move. It is called relaxation. Relaxing an edge means one simple thing. You check if going through this edge gives a cheaper way to reach a vertex. If it does, you update the cost.

Here is the rule for an edge from u to v with weight w:

• If dist[u] + w is smaller than dist[v], then we found a cheaper path. So set dist[v] = dist[u] + w.
• Otherwise, leave it alone.

We start by setting the source distance to 0 and every other distance to infinity. Infinity means “not reachable yet”. Then we relax edges again and again until nothing improves.

🔁 Why Relax V-1 Times?

Now think about how long a shortest path can get. In a graph with V vertices, the longest a shortest path can ever be is V-1 edges. Why? Because a shortest path never repeats a vertex. If it did, it would contain a loop. And removing that loop would make it shorter or equal. So with V vertices, you can touch at most V of them. That is V-1 edges between them.

So we do this:

• Pass 1 settles all shortest paths that use 1 edge.
• Pass 2 settles all shortest paths that use up to 2 edges.
• And so on, up to pass V-1.

After V-1 passes, every real shortest path is final. That is why we loop V-1 times.

Now the negative-cycle check. After V-1 passes everything should be settled. So we run one more pass. If any edge can still be relaxed, that means costs keep dropping with no bottom. That can only happen if a negative cycle exists.

🗺️ A Small Example Graph

Let’s use a tiny graph with four vertices: 0, 1, 2, 3. Vertex 0 is our source. Notice the negative edge from 2 to 1.

Let’s trace it by hand. We start with dist[0] = 0 and the rest as infinity.

See how reaching 1 directly costs 4, but going 0 to 2 to 1 costs only 2? That is because of the negative edge. Dijkstra would have locked in the 4 too early and missed this. Bellman-Ford keeps relaxing, so it catches it.

🪜 Steps to Run Bellman-Ford

Here is the full recipe, in order:

1. Set dist[source] = 0 and dist[v] = infinity for every other vertex.
2. Repeat V-1 times: go through every edge (u, v, w) and relax it.
3. Do one final pass over all edges. If any edge can still be relaxed, report a negative cycle.
4. If no edge improves on that final pass, the dist array holds the real shortest distances.

Notice that each pass touches every edge in the graph. The order you visit them does not change the final answer.

💻 Bellman-Ford in Code

Now let’s turn that recipe into a program. We store the graph as a simple list of edges, where each edge is (u, v, w). We run the relaxation passes. Then we do the one extra check for a negative cycle. Finally we print the distances from source 0.

#include <stdio.h>
#include <limits.h>

#define V 4
#define E 5

// Each edge is u -> v with weight w
int edgeU[E] = {0, 0, 2, 1, 2};
int edgeV[E] = {1, 2, 1, 3, 3};
int edgeW[E] = {4, 5, -3, 3, 2};

void bellmanFord(int source) {
    long dist[V];
    // Step 1: every distance starts as "infinity", source is 0
    for (int i = 0; i < V; i++) dist[i] = LONG_MAX;
    dist[source] = 0;

    // Step 2: relax all edges V-1 times
    for (int pass = 0; pass < V - 1; pass++) {
        for (int e = 0; e < E; e++) {
            int u = edgeU[e], v = edgeV[e], w = edgeW[e];
            if (dist[u] != LONG_MAX && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
        }
    }

    // Step 3: one more pass to detect a negative cycle
    for (int e = 0; e < E; e++) {
        int u = edgeU[e], v = edgeV[e], w = edgeW[e];
        if (dist[u] != LONG_MAX && dist[u] + w < dist[v]) {
            printf("Negative cycle detected\n");
            return;
        }
    }

    // Step 4: print the shortest distances
    for (int i = 0; i < V; i++)
        printf("Distance to %d = %ld\n", i, dist[i]);
}

int main() {
    bellmanFord(0);
    return 0;
}

Distance to 0 = 0
Distance to 1 = 2
Distance to 2 = 5
Distance to 3 = 5

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

struct Edge { int u, v, w; };

void bellmanFord(vector<Edge>& edges, int V, int source) {
    vector<long> dist(V, LONG_MAX);
    dist[source] = 0; // source starts at 0

    // Relax all edges V-1 times
    for (int pass = 0; pass < V - 1; pass++) {
        for (auto& e : edges) {
            if (dist[e.u] != LONG_MAX && dist[e.u] + e.w < dist[e.v])
                dist[e.v] = dist[e.u] + e.w;
        }
    }

    // One extra pass to check for a negative cycle
    for (auto& e : edges) {
        if (dist[e.u] != LONG_MAX && dist[e.u] + e.w < dist[e.v]) {
            cout << "Negative cycle detected" << endl;
            return;
        }
    }

    for (int i = 0; i < V; i++)
        cout << "Distance to " << i << " = " << dist[i] << endl;
}

int main() {
    vector<Edge> edges = {{0,1,4}, {0,2,5}, {2,1,-3}, {1,3,3}, {2,3,2}};
    bellmanFord(edges, 4, 0);
    return 0;
}

Distance to 0 = 0
Distance to 1 = 2
Distance to 2 = 5
Distance to 3 = 5

public class BellmanFord {
    // Each row is {u, v, w}
    static int[][] edges = {{0,1,4}, {0,2,5}, {2,1,-3}, {1,3,3}, {2,3,2}};

    static void bellmanFord(int V, int source) {
        long[] dist = new long[V];
        for (int i = 0; i < V; i++) dist[i] = Long.MAX_VALUE;
        dist[source] = 0; // source starts at 0

        // Relax all edges V-1 times
        for (int pass = 0; pass < V - 1; pass++) {
            for (int[] e : edges) {
                if (dist[e[0]] != Long.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]])
                    dist[e[1]] = dist[e[0]] + e[2];
            }
        }

        // Extra pass: detect a negative cycle
        for (int[] e : edges) {
            if (dist[e[0]] != Long.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {
                System.out.println("Negative cycle detected");
                return;
            }
        }

        for (int i = 0; i < V; i++)
            System.out.println("Distance to " + i + " = " + dist[i]);
    }

    public static void main(String[] args) {
        bellmanFord(4, 0);
    }
}

Distance to 0 = 0
Distance to 1 = 2
Distance to 2 = 5
Distance to 3 = 5

def bellman_ford(edges, V, source):
    # Step 1: every distance is infinity, source is 0
    dist = [float("inf")] * V
    dist[source] = 0

    # Step 2: relax all edges V-1 times
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] != float("inf") and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # Step 3: one more pass to detect a negative cycle
    for u, v, w in edges:
        if dist[u] != float("inf") and dist[u] + w < dist[v]:
            print("Negative cycle detected")
            return

    # Step 4: print the shortest distances
    for i in range(V):
        print(f"Distance to {i} = {dist[i]}")


# edges as (u, v, w)
graph = [(0, 1, 4), (0, 2, 5), (2, 1, -3), (1, 3, 3), (2, 3, 2)]
bellman_ford(graph, 4, 0)

Distance to 0 = 0
Distance to 1 = 2
Distance to 2 = 5
Distance to 3 = 5

function bellmanFord(edges, V, source) {
  // Step 1: every distance is Infinity, source is 0
  const dist = new Array(V).fill(Infinity);
  dist[source] = 0;

  // Step 2: relax all edges V-1 times
  for (let pass = 0; pass < V - 1; pass++) {
    for (const [u, v, w] of edges) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
      }
    }
  }

  // Step 3: one more pass to detect a negative cycle
  for (const [u, v, w] of edges) {
    if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
      console.log("Negative cycle detected");
      return;
    }
  }

  // Step 4: print the shortest distances
  for (let i = 0; i < V; i++) {
    console.log(`Distance to ${i} = ${dist[i]}`);
  }
}

// edges as [u, v, w]
const graph = [[0, 1, 4], [0, 2, 5], [2, 1, -3], [1, 3, 3], [2, 3, 2]];
bellmanFord(graph, 4, 0);

Distance to 0 = 0
Distance to 1 = 2
Distance to 2 = 5
Distance to 3 = 5

Look at the distance to vertex 1. It came out as 2, not 4. That is the negative edge from 2 to 1 lowering the cost. Bellman-Ford caught it because it kept relaxing.

⏱️ How Slow Is It?

We loop V-1 times. Inside each loop we touch every edge E. So the work is roughly V times E.

For dense graphs, where E can be close to V squared, this becomes about O(V^3). That is the price you pay for handling negative edges.

⚖️ Bellman-Ford vs Dijkstra

Both find single-source shortest paths. So when do you reach for which one? Here is the honest comparison.

The short version: if every weight is positive, use Dijkstra because it is faster. The moment a negative weight shows up, switch to Bellman-Ford.

⚠️ Common Mistakes

A few traps students fall into:

• Stopping after one pass. You must repeat the relaxation V-1 times, not just once.
• Skipping the extra pass. Without that final check you never find out about a negative cycle, and your distances are quietly wrong.
• Adding weight to an “infinity” distance. If dist[u] is still infinity, that vertex is not reachable yet, so do not relax from it. Notice every code sample checks for this first.
• Using Dijkstra on a graph with negative edges. It runs, it gives an answer, but the answer is wrong. And a wrong answer that looks fine is very hard to catch.

🧩 What You’ve Learned

✅ Bellman-Ford finds shortest paths from one source to all vertices, even with negative edge weights.

✅ Relaxation is the one core move: if dist[u] + w beats dist[v], update dist[v].

✅ We relax every edge V-1 times because a shortest path has at most V-1 edges.

✅ One extra pass that still improves means there is a negative cycle, so no valid shortest path exists.

✅ The time complexity is O(V * E), slower than Dijkstra but able to handle negative weights.

🚀 What’s Next?

• Dijkstra Shortest Path Algorithm
• Floyd-Warshall Algorithm