Module A-7·12 min read

Handling negative weights, detecting negative cycles, and all-pairs shortest paths.

Written by Jatin Jain Saraf · Architect of SupraScan

Module A-7 — Shortest Paths II: Bellman-Ford and Floyd-Warshall

What this module covers: Module A-6 flagged Dijkstra's one hard requirement: non-negative edge weights. This module covers the algorithm that handles negative weights correctly — Bellman-Ford — plus how to detect a negative cycle (a path that can be made arbitrarily cheap by looping forever), and Floyd-Warshall, which computes shortest paths between every pair of nodes at once, built directly on Module P-13/P-14's dynamic programming patterns.

Bellman-Ford: Relax Every Edge, Repeatedly

Where Dijkstra greedily commits to one node at a time (and breaks on negative weights because of that commitment), Bellman-Ford takes a much more repetitive, less clever approach that happens to be exactly what makes it correct even with negative edges: relax every single edge, V − 1 times, where "relax" means "check if going through this edge would improve the known distance to its destination, and update if so."

function bellmanFord(
  edges: [string, string, number][], // [from, to, weight][]
  vertices: string[],
  start: string
): Map<string, number> | null {
  const distances = new Map<string, number>();
  for (const v of vertices) distances.set(v, Infinity);
  distances.set(start, 0);
 
  // Relax every edge, V - 1 times — enough for a shortest path to "propagate" across the whole graph
  for (let i = 0; i < vertices.length - 1; i++) {
    for (const [from, to, weight] of edges) {
      const distFrom = distances.get(from)!;
      if (distFrom !== Infinity && distFrom + weight < distances.get(to)!) {
        distances.set(to, distFrom + weight); // found a cheaper way to reach `to`
      }
    }
  }
 
  // One more pass: if any distance can still improve, a negative cycle exists
  for (const [from, to, weight] of edges) {
    const distFrom = distances.get(from)!;
    if (distFrom !== Infinity && distFrom + weight < distances.get(to)!) {
      return null; // negative cycle detected — shortest path is not well-defined
    }
  }
 
  return distances;
}

Why exactly V − 1 passes: the shortest path between any two nodes, if one exists, uses at most V − 1 edges (a path can't usefully visit more than every node once — visiting a node twice would mean it contains a cycle, which is never necessary in a shortest path unless that cycle is negative). Each full pass over every edge can extend the "settled" shortest-path knowledge by one additional edge of depth, so after V − 1 passes, every shortest path — however many edges it needs, up to that maximum — has had enough opportunity to fully propagate through relaxation. This repetitive brute-force approach, unlike Dijkstra's greedy commitment, never permanently rules out revisiting a node's distance, which is exactly why negative edges don't break it: nothing is ever assumed "final" until all V − 1 passes complete.

Detecting Negative Cycles

If a graph contains a cycle whose total weight is negative, "shortest path" stops being well-defined for any node reachable from that cycle — you could keep looping around it, making the total cost lower and lower forever, with no actual minimum. Bellman-Ford detects this directly: after V − 1 relaxation passes should have already found every genuine shortest path, one more pass that still finds an improvement means the graph must contain a negative cycle — because there's no other way a legitimate shortest path could take more than V − 1 edges to settle. This is a real, practical capability Dijkstra has no equivalent for at all: Dijkstra's greedy strategy doesn't just fail silently in the presence of negative cycles — it has no built-in way to notice the problem exists in the first place.

Floyd-Warshall: Every Pair, at Once

Sometimes the actual question isn't "shortest path from one specific start" but "shortest path between every pair of nodes." Running Bellman-Ford (or Dijkstra) from every single node individually would work, but Floyd-Warshall computes all pairs directly, using a dynamic programming recurrence in the exact spirit of Modules P-13 and P-14:

function floydWarshall(vertices: string[], edges: [string, string, number][]): Map<string, Map<string, number>> {
  const dist = new Map<string, Map<string, number>>();
 
  for (const u of vertices) {
    dist.set(u, new Map());
    for (const v of vertices) {
      dist.get(u)!.set(v, u === v ? 0 : Infinity);
    }
  }
  for (const [from, to, weight] of edges) {
    dist.get(from)!.set(to, weight);
  }
 
  // Try every node k as a possible "intermediate stop" between every pair (i, j)
  for (const k of vertices) {
    for (const i of vertices) {
      for (const j of vertices) {
        const throughK = dist.get(i)!.get(k)! + dist.get(k)!.get(j)!;
        if (throughK < dist.get(i)!.get(j)!) {
          dist.get(i)!.set(j, throughK); // routing through k is cheaper than the current known path
        }
      }
    }
  }
 
  return dist;
}