• Overview: APSP Settings
• Floyd–Warshall (DP on triples)
• Johnson's Algorithm (Reweight + Dijkstra)
• When to use which
• Exercises

• APSP: shortest distances between all pairs of vertices.
• Floyd–Warshall: dense graphs, small n (O(n^3)). Handles negatives, detects cycles.
• Johnson: sparse graphs, larger n. Reweight with potentials then run Dijkstra from every node.

// dist: n x n matrix (Infinity where no edge), dist[i][i] = 0
function floydWarshall(dist) {
  const n = dist.length;
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      const dik = dist[i][k];
      if (dik === Infinity) continue;
      for (let j = 0; j < n; j++) {
        const cand = dik + dist[k][j];
        if (cand < dist[i][j]) dist[i][j] = cand;
      }
    }
  }
  // Negative cycle detection: dist[i][i] < 0 implies i is on/affected by a neg cycle
  const neg = Array(n).fill(false);
  for (let i = 0; i < n; i++) if (dist[i][i] < 0) neg[i] = true;
  return { dist, negCycleOn: neg };
}

• Path reconstruction: keep next/parent matrix and update on relaxations.
• Optimization: block FW for cache performance on large n.

// Graph as adjacency list: adj[u] = [{to, w}, ...]
// Returns matrix D of all-pairs distances or throws if negative cycle
function johnson(adj) {
  const n = adj.length;
  // Add super-source s' connected to all nodes with 0-weight edges
  const edges = [];
  for (let u = 0; u < n; u++) {
    for (const {to: v, w} of adj[u]) edges.push({u, v, w});
    edges.push({u: n, v: u, w: 0});
  }
  // Bellman–Ford from s'
  const { dist: h, negCycle } = (function bellmanFord() {
    const dist = Array(n + 1).fill(Infinity); dist[n] = 0;
    for (let i = 0; i < n; i++) {
      let any = false;
      for (const {u, v, w} of edges) {
        if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
          dist[v] = dist[u] + w; any = true;
        }
      }
      if (!any) break;
    }
    let neg = false;
    for (const {u, v, w} of edges) if (dist[u] !== Infinity && dist[u] + w < dist[v]) neg = true;
    return { dist: dist.slice(0, n), negCycle: neg };
  })();
  if (negCycle) throw new Error('Negative cycle detected');
  // Reweight edges w' = w + h[u] - h[v]
  const adj2 = Array.from({length: n}, () => []);
  for (let u = 0; u < n; u++) for (const {to: v, w} of adj[u]) adj2[u].push({to: v, w: w + h[u] - h[v]});
  // Run Dijkstra from each node on reweighted graph
  const D = Array.from({length: n}, () => Array(n).fill(Infinity));
  function dijkstraOnce(s) {
    const dist = Array(n).fill(Infinity); dist[s] = 0;
    const heap = [];
    const up = (i) => { while (i) { const p = (i - 1) >> 1; if (heap[p][0] <= heap[i][0]) break; [heap[p], heap[i]] = [heap[i], heap[p]]; i = p; } };
    const down = (i) => { for (;;) { let l = i*2+1, r = l+1, m = i; if (l < heap.length && heap[l][0] < heap[m][0]) m = l; if (r < heap.length && heap[r][0] < heap[m][0]) m = r; if (m === i) break; [heap[m], heap[i]] = [heap[i], heap[m]]; i = m; } };
    const push = (x) => { heap.push(x); up(heap.length - 1); };
    const pop = () => { const t = heap[0]; const last = heap.pop(); if (heap.length) { heap[0] = last; down(0); } return t; };
    push([0, s]);
    while (heap.length) {
      const [d, u] = pop(); if (d !== dist[u]) continue;
      for (const {to: v, w} of adj2[u]) if (d + w < dist[v]) { dist[v] = d + w; push([dist[v], v]); }
    }
    return dist;
  }
  for (let s = 0; s < n; s++) {
    const d = dijkstraOnce(s);
    for (let v = 0; v < n; v++) if (d[v] < Infinity) D[s][v] = d[v] - h[s] + h[v];
  }
  return D;
}

• Why it works: reweighting preserves shortest paths and removes negative edges.
• Complexity: O(n·(m log n)) after one BF pass.

• Use Floyd–Warshall for dense graphs (n ≤ ~500–700 in JS) or when you need simple implementation and negative-edge support.
• Use Johnson for sparse graphs and larger n; requires no negative cycles.

1. Implement Floyd–Warshall with path reconstruction (next matrix).
2. Implement Johnson and verify results against repeated Dijkstra on non-negative graphs.
3. Generate random sparse graphs and compare runtime vs. Floyd–Warshall.