Bellman-Ford

DSA · Graphs

Theory

Bellman-Ford computes shortest paths from one source even when some edge weights are negative. It relaxes every edge V-1 times, because a shortest path can contain at most V-1 edges. A further round that still improves a distance proves there is a negative-weight cycle, where costs can be lowered forever. It runs in O(V × E), slower than Dijkstra.

Why we use it

It handles negative weights and detects negative cycles, which Dijkstra cannot.

When to use it

Use it for currency arbitrage detection, financial graphs with credits and debits, and routing protocols such as RIP.

How it works

  1. dist[source] = 0, others infinity
  2. Repeat V - 1 times: relax every edge
  3. Run one more pass over all edges
  4. Any distance still improves? Yes: Negative cycle exists. No: Distances are final.
  5. Done

Syntax

dist[src] = 0
repeat V-1 times:
    for (u, v, w) in edges:
        if dist[u] + w < dist[v]: dist[v] = dist[u] + w
one more pass improves anything -> negative cycle

Time: O(V·E)

Example

vertices = ["A", "B", "C", "D"]
edges = [("A", "B", 4), ("A", "C", 5), ("B", "C", -3), ("C", "D", 4), ("B", "D", 6)]

def bellman_ford(src):
    dist = {v: float("inf") for v in vertices}
    dist[src] = 0
    for _ in range(len(vertices) - 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]:
            return None
    return dist

print("Shortest distances:", bellman_ford("A"))
edges.append(("D", "B", -5))
print("With a negative cycle:", bellman_ford("A"))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic