Bellman-Ford

Bellman-Ford finds the shortest path from one source to every other node — and unlike Dijkstra, it works even when edges carry negative weights (think refunds, or a downhill stretch). It buys that power with brute repetition: it simply relaxes every edge, over and over, until the distances stop changing.

Why exactly V−1 passes

A shortest path in a graph of V vertices can cross at most V − 1 edges — any more and it would repeat a vertex, forming a loop you could cut out. Each full pass over all edges lets correct distance information advance one more edge along every path. So after V − 1 passes, the information has had time to reach the end of even the longest possible shortest path, and all distances are final.

1. 1Set dist[source] = 0 and every other distance to ∞.
2. 2Relax every edge (u, v, w): if dist[u] + w < dist[v], lower dist[v].
3. 3Repeat that full sweep V − 1 times.
4. 4Do one extra sweep: if any edge can *still* be relaxed, a negative cycle is reachable.

function bellmanFord(V, edges, source) {
  const dist = Array(V).fill(Infinity);
  dist[source] = 0;
  for (let pass = 0; pass < V - 1; pass++) {      // V-1 sweeps
    for (const { u, v, w } of edges) {
      if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;  // relax
    }
  }
  for (const { u, v, w } of edges) {             // one more sweep
    if (dist[u] + w < dist[v]) throw new Error('negative cycle');
  }
  return dist;
}