Why use Bellman-Ford over Dijkstra?

Bellman-Ford handles negative edge weights and can detect negative cycles, which Dijkstra's algorithm cannot.

How does it detect negative cycles?

After relaxing all edges V-1 times, if any edge can still be relaxed on the Vth pass, it means a negative cycle exists.

What is the time complexity of Bellman-Ford?

O(V * E), which is slower than Dijkstra but necessary for graphs with potential negative cycles.

Bellman-Ford Algorithm

The Bellman-Ford algorithm finds the shortest paths from a source in a graph that may contain negative-weight edges, and detects negative-weight cycles.

INIT

Distances before the first pass

A:0

B:∞

C:∞

D:∞

Edge list (walked in order)

A→B:4

A→C:2

B→C:-3

B→D:2

C→D:3

Every distance starts at ∞ except A, which is 0.

Pass 1 of 3: walk the whole edge list and relax whatever will relax.

Intuition

Unlike Dijkstra, which aggressively chooses the shortest known path, Bellman-Ford is cautious.

It assumes any path could be improved by any edge, so it iteratively checks all edges to see if they can offer a shortcut.

This careful approach allows it to handle negative edge weights.

Concept

Relaxation: Checking if an edge (u, v) with weight w allows us to reach v cheaper than before (dist[v] > dist[u] + w).
V-1 Iterations: In a graph with V nodes, the longest simple path can have at most V-1 edges. Repeating relaxation V-1 times guarantees finding shortest simple paths.
Negative Cycle: If we can still relax an edge after V-1 iterations, it means there's a cycle that reduces total distance forever (Negative Cycle).

How it Works

Algorithm Steps:

Initialize distances: dist[start] = 0, others = ∞.
Repeat V-1 times:
- Iterate through all edges (u, v, w).
- If dist[u] + w < dist[v], update dist[v] = dist[u] + w.
Check for Negative Cycles:
- Iterate through all edges one more time.
- If any edge can still be relaxed, a negative cycle exists.

Step-by-Step Breakdown

Watch the visualization:

Blue edge: The edge being checked in the current pass.
Green node: Has a finite distance from the start.
Red edge and its two nodes: An edge that still improves a distance after V - 1 passes: a negative cycle.
Number above a node: Its current distance from the start.

When to Use

Use Bellman-Ford when:

The graph contains negative edge weights.
You need to detect negative cycles (e.g., currency arbitrage).
The graph is small enough (O(VE) is slower than Dijkstra O(E log V)).

When NOT to Use

Positive Weights Only: Dijkstra's is significantly faster.
Large Graphs: O(VE) complexity makes it impractical for very large networks.

How to Identify

"Shortest path with negative weights", "Detect negative cycle", "Arbitrage opportunities".

Sample Problems

Network Delay Time

Can be solved with Bellman-Ford (though Dijkstra is standard).

Cheapest Flights Within K Stops

A variant of Bellman-Ford where we limit relaxations to K iterations.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description

Dijkstra's Algorithm

Minimum Spanning Tree