Bellman-Ford

O(V·E)

Bellman-Ford computes single-source shortest paths by relaxing every edge in the graph, repeated up to V−1 times (any shortest path has at most V−1 edges). It's slower than Dijkstra at O(V·E), but unlike Dijkstra it works with negative edge weights and can detect negative cycles. Here the weights are positive distances, so it lands on the same answer as Dijkstra — what differs is the relax-every-edge process.

Click empty space = vertex · click two vertices = edge · drag = moveStart: A
Input graph
Edit the input and press Play

How it works

  1. Set the start's distance to 0 and every other to ∞.
  2. In each round, relax every edge: if going through u shortens v, update it.
  3. Repeat for up to V−1 rounds.
  4. Stop early once a full round changes nothing.

Pseudocode

1bellmanFord(graph, start):          # O(V·E)2  dist[start] ← 0; all others ← ∞3  repeat V-1 times:4    for every edge (u, v):5      if dist[u] + w(u,v) < dist[v]:6        dist[v] ← dist[u] + w(u,v)    # relax7    stop early if nothing changed