Algorithm Guidecomplexity: O(V·E)

Bellman-Ford

A shortest-path algorithm that works even with negative edges. Relaxing every edge V−1 times converges to the shortest distances, and one extra relaxation detects a negative cycle. Slower than Dijkstra, but more general.

01Bellman-Ford

Explore How It Works

Starting Bellman-Ford. The source is 0 and the rest ∞. Sweep every edge three times over — negative weights included.

Pass 1 · start with the edge from B to D. There is still no route to B, so there is nothing to add — skip it.

Going from A to B costs 4. It is the first measurement, so write it down as is.

Going from A to C costs 5. First measurement here too, written down as is.

The edge from C to B weighs −3. Coming through C gives 2, shorter than the 4 just written.

Going from C to D costs 11. That completes the first sweep.

Pass 2 · now that B has dropped to 2, D shortens to 5 as well — an improvement a single sweep could never reach.

The remaining edges have nothing left to lower. The second sweep ends with no update.

Pass 3 · another look at every edge changes nothing, so it has converged. Next, check for a negative cycle.

Done · shortest path from A to D is A → C → B → D (distance 5). No negative cycle, so the result is valid.

Live Python

1def bellman_ford(edges, V, start):

2 dist = [INF] * V

# dist[A] = 0

3 dist[start] = 0

4 for i in range(V - 1):

5 for u, v, w in edges:

6 if dist[u] + w < dist[v]:

7 dist[v] = dist[u] + w

8 for u, v, w in edges: # negative cycle check

9 if dist[u] + w < dist[v]:

10 raise ValueError('negative cycle')

11 return dist

1 / 10

02 Understand It Simply

For Everyone

🔑How It Works

Sweeps every edge as many times as there are vertices, relaxing any shorter path it finds. Slower, but it handles negative weights and detects negative cycles.

💡In Plain Words

Relaxes every edge V−1 times to find the shortest distances.

Slow, but it handles negative edges and detects negative cycles.

📍Where It's Used

–Graphs with negative edges
–currency-arbitrage detection

03 Python Implementation

A clean, readable reference implementation of the core logic of Bellman-Ford.

core_implementation.py

def bellman_ford(edges, V, start):
    dist = [float("inf")] * V
    dist[start] = 0
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            raise ValueError("negative cycle")
    return dist

04 Frequently Asked Questions

FAQ

What is Bellman-Ford?+

What is the time complexity of Bellman-Ford?+

The time complexity of Bellman-Ford is O(V·E). Follow the step-by-step visualization to see exactly why.

Where is Bellman-Ford used?+

Graphs with negative edges, currency-arbitrage detection.

What's a simple analogy for Bellman-Ford?+

Sweeps every edge as many times as there are vertices, relaxing any shorter path it finds. Slower, but it handles negative weights and detects negative cycles.

→ Graphs — see allRelated