Bellman-Ford Algorithm Visualizer

How it works

1. Set dist[s] = 0 and every other distance to ∞.
2. Repeat V − 1 times: for every edge u → v with weight w, if dist[u] + w < dist[v], lower dist[v] and set parent[v] = u.
3. If a whole pass changes nothing, stop early — every distance is already final.
4. Run one more pass over all edges. If any edge can still be relaxed, a negative cycle is reachable from s and shortest paths are undefined.
5. Otherwise dist holds the shortest distances; follow parent pointers to rebuild each path.

Why V − 1 passes are enough

After pass k, dist[v] is at most the cost of the cheapest path from s to v that uses at most k edges. A shortest path never repeats a node (if there is no negative cycle, a repeated loop would not make it cheaper), so it has at most V − 1 edges — and after V − 1 passes every such path has been fully relaxed, edge by edge.

This is dynamic programming over the number of edges. The order of the edges inside a pass only changes how fast the distances converge — a lucky order can finish in a single pass — never the final answer.

Worked example with a negative edge

The page opens on the directed graph A → B 2, A → C 5, C → B −4, B → D 3, D → E 1, C → E 8. Each pass relaxes the edges in the order A → B, A → C, B → D, C → B, C → E, D → E:

• Pass 1: B = 2, C = 5, D = 5 (through B). Then C → B gives 5 − 4 = 1, so B drops to 1. E becomes 13 through C, then 6 through D.
• Pass 2: B → D now gives 1 + 3 = 4 (D: 5 → 4), and D → E gives 5 (E: 6 → 5).
• Pass 3: nothing changes, so the algorithm stops after 3 of the allowed V − 1 = 4 passes.

Result: B 1 via A → C → B, C 5, D 4, E 5. Dijkstra on the same graph finalizes B at 2 too early and reports D = 5 and E = 6 — run both in the visualizer and compare.

Negative cycles

A negative cycle is a cycle whose weights add up to less than zero, such as B → C → D → B with weights −2, 3 and −3 (total −2). Every lap makes the route cheaper, so nodes reachable through it have no shortest path at all. Bellman-Ford detects this because after V − 1 passes some edge on the cycle can still be relaxed.

To print the cycle, take a node relaxed in the extra pass, follow parent pointers V times to be sure you are inside the cycle, then follow them until you return to the same node. Only cycles reachable from s are detected; to find any negative cycle, add a virtual source with a 0-weight edge to every node. In an undirected graph one negative edge is already a negative cycle (u → v → u), so Bellman-Ford is really a directed-graph algorithm.

Bellman-Ford vs Dijkstra

• Weights: Bellman-Ford accepts any weights; Dijkstra needs every weight ≥ 0.
• Speed: O(V · E) versus O((V + E) log V) — on large graphs Dijkstra is dramatically faster.
• Negative cycles: Bellman-Ford detects them; Dijkstra silently gives wrong answers.
• Structure: Bellman-Ford just loops over an edge list, which makes it easy to distribute: its "tell your neighbours your distance" rule is the basis of distance-vector routing (RIP), while Dijkstra underlies link-state routing (OSPF).
• SPFA, a queue-based variant that only re-relaxes edges out of nodes whose distance changed, is often faster on average but has the same O(V · E) worst case.

Common mistakes and uses

• Relaxing from unreachable nodes: in C++ or Java, INF + w with a negative w looks like an improvement (or overflows). Skip edges whose source distance is still infinite.
• Skipping the extra pass, so negative cycles go unnoticed and the distances are garbage.
• Using it on undirected graphs with negative edges, where every negative edge is a cycle.

Real uses: currency arbitrage (weight each exchange by −log(rate); a negative cycle is a profitable loop), systems of difference constraints (x_j − x_i ≤ w), Johnson's all-pairs algorithm, and the interview problem "cheapest flights within K stops", which runs K + 1 passes using a copy of the previous pass's distances.

Time and space complexity

Bellman-Ford Algorithm in Python

import math


def bellman_ford(nodes, edges, s):
    """edges: [(u, v, w)] - list both directions for an undirected graph.
    Returns dist, or None if a negative cycle is reachable from s."""
    dist = {v: math.inf for v in nodes}
    dist[s] = 0
    for _ in range(len(nodes) - 1):        # repeat V - 1 times
        changed = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:      # inf + w stays inf
                dist[v] = dist[u] + w
                changed = True
        if not changed:
            break                          # stop early
    for u, v, w in edges:                  # one extra pass
        if dist[u] + w < dist[v]:
            return None                    # still relaxes: negative cycle!
    return dist

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• Dijkstra's Algorithm VisualizerDijkstra's algorithm finds the shortest paths from one node in a graph with non-negative weights. Watch every relaxation step by step, with heap-based code.
• Topological Sort VisualizerA topological sort orders the nodes of a DAG so every edge points forward. Watch Kahn's algorithm step by step, see why cycles block it, and get the code.
• BFS Visualizer — Breadth-First SearchBreadth-first search explores a graph level by level with a queue and finds fewest-edge paths. Watch BFS run step by step, with code and O(V + E) analysis.
• Graph Algorithm VisualizerInteractive graph algorithm visualizer: draw or generate a graph and step through BFS, DFS, Dijkstra, Bellman-Ford, Kruskal, Prim, topological sort and SCCs.