Bellman-Ford and Floyd-Warshall

A courier drives one-way legs between four depots: S, A, B and C. Each leg costs fuel. One leg is different: whoever drives from B to A carries a paid parcel, and the pay is 4 more than the fuel. So that leg's cost is −4. The courier starts at S and wants the cheapest way to reach each depot.

Try Dijkstra's rule, "settle the closest place first". S→A costs 1 and S→B costs 2, so A is settled first, at 1, and C gets 1 + 3 = 4. Next B reveals S→B→A, which costs 2 − 4 = −2. But A was already "final", so C ends at 4 when it should be 1. With a negative cost, a place that looks far away can lead somewhere cheaper, so settling the closest first is no longer safe.

The heap code in the Dijkstra lesson never marks a place as settled, so here it would push A again and patch C. On other graphs that patching can snowball into an exponential amount of work, and a negative loop makes it run forever.

#Bellman-Ford: relax every edge, every round

Bellman-Ford gives up on choosing a clever order. Each round, it relaxes every edge, in any fixed order: if dist[u] + cost beats dist[v], lower dist[v]. Then it does that again.

Here is why that is enough. After round 1, every cheapest route of one edge is counted. A cheapest route of 2 edges is a 1-edge route plus one more edge, and round 2 relaxes that edge. So after round k, every cheapest route with up to k edges is counted. Without a loop of negative total cost, a cheapest route never visits a place twice, so it has at most V − 1 edges. V − 1 rounds always finish the job.

dist[start] = 0, all others ∞repeat V − 1 times:  for each edge (u, v, cost):    if dist[u] + cost < dist[v]:      dist[v] = dist[u] + costfor each edge: if it still improves → negative cycle

Edge order affects speed, not correctness. This order was unlucky: the news about A took a full round to reach C. The code stops early when a round changes nothing.

// edges: list of [from, to, cost], one-way. nodes: list of names.
function bellmanFord(nodes, edges, start) {
  const dist = {};
  for (const node of nodes) dist[node] = Infinity;
  dist[start] = 0;
  for (let round = 1; round < nodes.length; round++) { // V - 1 rounds
    let changed = false;
    for (const [u, v, cost] of edges) {
      if (dist[u] + cost < dist[v]) {
        dist[v] = dist[u] + cost;
        changed = true;
      }
    }
    if (!changed) break; // nothing moved: every distance is final
  }
  for (const [u, v, cost] of edges) {
    if (dist[u] + cost < dist[v]) return null; // still improving: negative cycle
  }
  return dist;
}
// bellmanFord(["S", "A", "B", "C"], edges, "S") → { S: 0, A: -2, B: 2, C: 1 }

import math
 
# edges: list of (from, to, cost), one-way. nodes: list of names.
def bellman_ford(nodes, edges, start):
    dist = {node: math.inf for node in nodes}
    dist[start] = 0
    for _ in range(len(nodes) - 1):  # V - 1 rounds
        changed = False
        for u, v, cost in edges:
            if dist[u] + cost < dist[v]:
                dist[v] = dist[u] + cost
                changed = True
        if not changed:
            break  # nothing moved: every distance is final
    for u, v, cost in edges:
        if dist[u] + cost < dist[v]:
            return None  # still improving: negative cycle
    return dist
 
# bellman_ford(["S", "A", "B", "C"], edges, "S") → {'S': 0, 'A': -2, 'B': 2, 'C': 1}

#Negative cycles

Suppose a new leg C→B appears with cost −2. Now B→A→C→B costs −4 + 3 − 2 = −3. Every lap of that loop makes the courier 3 richer, so there is no cheapest route any more. One more lap is always cheaper.

Bellman-Ford catches this. Without a negative cycle, everything is final after V − 1 rounds. So the code makes one extra pass: if any edge can still lower a distance, a negative loop is to blame, and the function returns null instead of wrong numbers.

#Floyd-Warshall: every pair at once

Now the dispatcher wants the cheapest cost from every depot to every other. You could run Bellman-Ford from each one. Floyd-Warshall does it with three short loops and one table.

The idea is to allow stopovers one depot at a time. Start with a table of direct legs. Then allow S as a stopover: for every pair i, j, check whether i → S → j is cheaper. Then add A, then B, then C. When you allow depot k, the best route from i to j either avoids k, so the table already has it, or goes through k once: the best i → k plus the best k → j, both already in the table.

dist = direct costs (0 on the diagonal, ∞ if no leg)for k in nodes:   # allow k as a stopover  for i in nodes:    for j in nodes:      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

// Places are numbered 0..n-1. edges: list of [from, to, cost], one-way.
function floydWarshall(n, edges) {
  const dist = Array.from({ length: n }, (_, i) =>
    Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity)));
  for (const [u, v, cost] of edges) dist[u][v] = Math.min(dist[u][v], cost);
  for (let k = 0; k < n; k++) {       // allow k as a stopover
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }
  return dist; // a negative dist[i][i] means i is on a negative cycle
}

import math
 
# Places are numbered 0..n-1. edges: list of (from, to, cost), one-way.
def floyd_warshall(n, edges):
    dist = [[0 if i == j else math.inf for j in range(n)] for i in range(n)]
    for u, v, cost in edges:
        dist[u][v] = min(dist[u][v], cost)
    for k in range(n):          # allow k as a stopover
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist  # a negative dist[i][i] means i is on a negative cycle

Negative cycles show up for free: a loop from i back to i with a negative total puts a negative number on the diagonal.

#Which one to use

#Common mistakes

#Check yourself

#What to practise next

Shortest paths answer "how do I get from here to there cheaply?". The last lesson in this module asks a different question: what is the cheapest set of links that connects every place at all? That is Minimum Spanning Trees, and it brings back Union-Find.