Bellman-Ford Shortest Paths

Single-source shortest paths with negative edge weights

Relax edges instead of finalizing vertices

A negative edge can improve a route after another vertex already looked settled, so the greedy guarantee used by Dijkstra no longer applies. Bellman-Ford repeatedly scans every directed edge and relaxes u -> v whenever dist[u] + w < dist[v].

Why V - 1 rounds are enough

A simple shortest path visits at most V - 1 edges. After round k, all shortest paths using at most k edges can be represented by the distance labels. The player highlights each scanned edge and updates the destination badge only when a shorter candidate is found.

Set source A to distance 0 and every other vertex to infinity.

1function bellmanFord(edges: [number, number, number][], n: number, source: number): number[] {
const dist = Array(n).fill(Infinity);
dist[source] = 0;
for (let k = 0; k < n - 1; k++) {
  for (const [u, v, w] of edges) {
    if (dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w;
    }
  }
}
return dist;
12}

Round k-

Total rounds V-14

Current edge-

Updates this round0

dist[A]0

dist[B]∞

dist[C]∞

dist[D]∞

dist[E]∞

1 / 34

Cost and negative-cycle detection

Scanning every edge for V - 1 rounds costs O(VE) time and O(V) distance storage. Run one additional round to detect a reachable negative cycle: if any distance still improves, no finite shortest path exists for vertices reachable from that cycle.

Use Bellman-Ford when negative weights are possible or negative-cycle detection matters. On a graph with non-negative weights, Dijkstra's algorithm is usually faster.

Algorithm Visualizer

Bellman-Ford Shortest Paths

Relax edges instead of finalizing vertices

Why V - 1 rounds are enough

Cost and negative-cycle detection