hardDSA

How does the Bellman-Ford algorithm work?

Q: How does the Bellman-Ford algorithm work?

**Intuition.** A shortest path in a graph with V vertices uses at most V − 1 edges. **Bellman-Ford** simply **relaxes every edge** V − 1 times: each pass lets correct distances propagate one edge further. Unlike Dijkstra it tolerates **negative edges**, and one extra pass that still improves something proves a **negative cycle**. relax all edges V-1 times; negative weights allowed 0 <circle cx="190" cy="40" r

844 views

Understand the problem

Explain Bellman-Ford and negative edges.

graphsshortest-path

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

Read the code

Edge relaxation + negative-cycle check

Run Playground

def bellman_ford(n, edges, source):
    INF = float('inf')
    dist = [INF] * n
    dist[source] = 0
    for _ in range(n - 1):                      # relax V-1 times
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:                        # one more pass detects a cycle
        if dist[u] != INF and dist[u] + w < dist[v]:
            return None                          # negative cycle
    return dist


# --- demo ---  edges (u, v, w); note negatives on 2->3 and 1->4
edges = [(0, 1, 6), (0, 2, 7), (1, 2, 8), (1, 3, 5),
         (2, 3, -3), (1, 4, -4), (3, 4, 9)]
print(bellman_ford(5, edges, 0))   # [0, 6, 7, 4, 2]

Join the discussion

Discussion (0)

No responses yet. Be the first to share what you think.

How do you serialize and deserialize a binary tree?

How do you solve the trapping rain water problem?