Negative Weights: Bellman-Ford and Floyd-Warshall

Dijkstra is fast because it commits. Once a node is locked in, it never looks at it again. That works because going further can only cost more, which stops being true the moment an edge is allowed to be negative.

Negative edges are not a made-up textbook scenario. A currency conversion that gains value, a chemical reaction that releases energy, a game move that refunds points. Any of those give you a graph where travelling an edge improves your position.

Bellman-Ford: stop being clever

Bellman-Ford drops the greedy selection completely. Instead of carefully picking the best node each round, it just relaxes every edge in the graph, then does it again, V minus 1 times total.

The reasoning is simpler than Dijkstra's. After one full pass, every correct one-edge path is settled. After two passes, every correct two-edge path. A shortest path can never use more than V minus 1 edges, because using V or more would mean visiting some node twice, and that means a cycle you could delete. So V minus 1 passes is always enough.

function bellmanFord(nodes, edges, start) {
  const dist = new Map(nodes.map((n) => [n, Infinity]));
  dist.set(start, 0);

  // V-1 passes. No cleverness about which edge to look at.
  for (let pass = 0; pass < nodes.length - 1; pass++) {
    let changed = false;

    for (const { from, to, weight } of edges) {
      if (dist.get(from) === Infinity) continue;   // no route here yet
      if (dist.get(from) + weight < dist.get(to)) {
        dist.set(to, dist.get(from) + weight);
        changed = true;
      }
    }

    if (!changed) break; // settled early, the rest of the passes are wasted
  }

  // One extra pass. If anything still improves, no shortest path exists.
  for (const { from, to, weight } of edges) {
    if (dist.get(from) === Infinity) continue;
    if (dist.get(from) + weight < dist.get(to)) {
      throw new Error("Negative cycle: shortest paths are undefined");
    }
  }

  return dist;
}

The negative cycle problem

That final pass is doing something more interesting than error handling. Picture a loop whose weights sum to a negative number. Go around it once and your total drops. Go around again and it drops further. There is no shortest path, because you can always beat any route by taking one more lap. The correct answer is negative infinity.

A --(1)---> B
B --(-3)--> C
C --(1)---> A

Loop total: 1 + (-3) + 1 = -1

Each lap costs -1, so "shortest" has no answer.
After V-1 passes everything should be settled. If another
pass still finds an improvement, a loop like this exists.

This detection has a genuinely useful application. Model currency exchange rates as a graph, take the negative logarithm of each rate as the edge weight, and a negative cycle is a sequence of trades that returns more money than you started with. Real trading systems look for exactly this.

Dijkstra or Bellman-Ford

Bellman-Ford is meaningfully slower. Use Dijkstra whenever your weights allow it, which in practice is most of the time, since distances and durations cannot be negative.

Floyd-Warshall: every pair at once

Both algorithms so far answer "shortest path from one source". Sometimes you want the distance between every pair of nodes. You could run Dijkstra V times. Or you could use Floyd-Warshall, which is five lines and works on an adjacency matrix.

// dist[i][j] starts as the direct edge weight, or Infinity if none.
// dist[i][i] starts at 0.

for (let k = 0; k < n; k++) {          // allowed intermediate node
  for (let i = 0; i < n; i++) {        // from
    for (let j = 0; j < n; j++) {      // to
      if (dist[i][k] + dist[k][j] < dist[i][j]) {
        dist[i][j] = dist[i][k] + dist[k][j];
      }
    }
  }
}

The loop order is the entire idea, and getting it backwards is the classic bug. The outer loop is not a counter, it is a question: "if I am now allowed to route through node k, does any pair get cheaper?" After k has ranged over every node, every possible intermediate has been considered.

It runs in O(V³) and needs O(V²) memory, so it is for small graphs. Handles negative edges fine. To spot a negative cycle, check whether any dist[i][i] ended up below zero, which would mean a node found a way back to itself at a profit.

Picking one, in one table

Check yourself

That covers the graph algorithms you will meet most often. If you want to feel the difference between BFS and Dijkstra again, the traversal and shortest-path widgets earlier in this section are worth replaying now that you know what the numbers mean.