• Overview and Assumptions
• Dijkstra with Binary Heap
• Bellman–Ford and Negative Cycles
• Variants and Notes
• Pitfalls
• Exercises

• Goal: compute shortest path distances from a source to all nodes.
• Dijkstra: requires non-negative edge weights; fast with a heap.
• Bellman–Ford: handles negative edges and detects negative cycles.

// adj: Array of arrays of {to, w}; 0-indexed nodes
function dijkstra(adj, s) {
  const n = adj.length;
  const dist = Array(n).fill(Infinity);
  const parent = Array(n).fill(-1);
  dist[s] = 0;
  // Simple binary heap implementation
  const heap = [];
  const push = (x) => { heap.push(x); up(heap.length - 1); };
  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 pop = () => { const top = heap[0]; const last = heap.pop(); if (heap.length) { heap[0] = last; down(0); } return top; };

  push([0, s]);
  while (heap.length) {
    const [d, u] = pop();
    if (d !== dist[u]) continue; // stale
    for (const {to: v, w} of adj[u]) {
      const nd = d + w;
      if (nd < dist[v]) { dist[v] = nd; parent[v] = u; push([nd, v]); }
    }
  }
  return { dist, parent };
}

function reconstructPath(parent, t) {
  const path = [];
  for (let v = t; v !== -1; v = parent[v]) path.push(v);
  return path.reverse();
}

• Complexity: O((n + m) log n) with binary heap; O(m + n log n) commonly.
• Non-negative weights only: otherwise correctness fails.

// edges: array of {u, v, w}; n nodes; returns {dist, parent, negCycle}
function bellmanFord(n, edges, s) {
  const dist = Array(n).fill(Infinity);
  const parent = Array(n).fill(-1);
  dist[s] = 0;
  for (let i = 0; i < n - 1; 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; parent[v] = u; any = true;
      }
    }
    if (!any) break;
  }
  // Detect negative cycle reachable from s
  const inNeg = Array(n).fill(false);
  for (const {u, v, w} of edges) {
    if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
      inNeg[v] = true;
    }
  }
  return { dist, parent, negCycle: inNeg.some(x => x) };
}

• Complexity: O(n·m).
• Detecting cycle set: BFS/DFS from initially flagged nodes to mark all affected vertices.

• 0-1 BFS: deque-based shortest paths when weights are 0 or 1.
• Dial's algorithm: buckets for small integer weights.
• SPFA: queue-based relaxation heuristic for sparse graphs; worst-case O(n·m).
• Potentials: Johnson's reweighting for APSP with negative edges but no negative cycles.

• Ensure non-negative weights before using Dijkstra.
• Beware overflow if weights are large; use 64-bit numbers where appropriate.
• Disconnected nodes remain at Infinity; handle gracefully in UI/outputs.

1. Implement Dijkstra with a binary heap and test on random sparse graphs.
2. Implement Bellman–Ford and print nodes affected by negative cycles.
3. Extend to 0-1 BFS and compare vs. Dijkstra on {0,1}-weighted graphs.