Sign in
Skip to solution
hardDSA

How does the Bellman-Ford algorithm work?

844 views
01

Understand the problem

Explain Bellman-Ford and negative edges.

graphsshortest-path
02

Attempt it yourself

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

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Bellman-Ford relaxes all edges V−1 times to find shortest paths from a source, handling negative weights (unlike Dijkstra). A V-th relaxation that still improves a distance reveals a negative cycle. Runs in O(V·E).

Solution ready — 2 min read

Classified // press E to declassify

04

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]
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

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

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 109 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track