Shortest Paths: BFS, Dijkstra, Bellman-Ford

// Template 1: BFS for unweighted graphs (every edge costs 1). Nodes leave the queue in order of
// distance, so the first time a node is reached is along a shortest path.
export function bfsDistances(n, edges, source) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) {
    adj[u].push(v);
    adj[v].push(u);                     // undirected: drop this line for a directed graph
  }
  const dist = new Array(n).fill(-1);   // -1 = not reached (yet)
  dist[source] = 0;
  const queue = [source];
  for (let head = 0; head < queue.length; head++) { // a head index: shift() is O(n)
    const u = queue[head];
    for (const v of adj[u]) {
      if (dist[v] !== -1) continue;
      dist[v] = dist[u] + 1;            // mark when pushed so nothing is queued twice
      queue.push(v);
    }
  }
  return dist;
}

import { MinHeap } from './min-heap.js';

// Template 2: Dijkstra for non-negative weights. Always expand the closest node not yet settled.
// Lazy deletion: instead of updating an entry inside the heap, push a new one and skip
// entries that are stale (a shorter distance was found after they were pushed).
export function dijkstra(n, edges, source) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v, w] of edges) adj[u].push([v, w]); // directed; also push [u, w] onto adj[v] if undirected
  const dist = new Array(n).fill(Infinity);
  dist[source] = 0;
  const heap = new MinHeap();
  heap.push([0, source]);
  while (heap.size > 0) {
    const [d, u] = heap.pop();
    if (d > dist[u]) continue;            // stale entry: u was settled with a smaller distance
    for (const [v, w] of adj[u]) {
      if (d + w < dist[v]) {
        dist[v] = d + w;
        heap.push([dist[v], v]);
      }
    }
  }
  return dist;                            // Infinity = unreachable
}

// The same loop with two extras: remember how each node was reached (prev) to rebuild the path,
// and stop as soon as the target is popped, because a popped node's distance is final.
export function shortestPath(n, edges, source, target) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v, w] of edges) adj[u].push([v, w]);
  const dist = new Array(n).fill(Infinity);
  const prev = new Array(n).fill(-1);
  dist[source] = 0;
  const heap = new MinHeap();
  heap.push([0, source]);
  while (heap.size > 0) {
    const [d, u] = heap.pop();
    if (d > dist[u]) continue;
    if (u === target) break;
    for (const [v, w] of adj[u]) {
      if (d + w < dist[v]) {
        dist[v] = d + w;
        prev[v] = u;
        heap.push([dist[v], v]);
      }
    }
  }
  if (dist[target] === Infinity) return { dist: -1, path: [] };
  const path = [];
  for (let v = target; v !== -1; v = prev[v]) path.push(v);
  return { dist: dist[target], path: path.reverse() };
}

// Template 3: Bellman-Ford. Each round relaxes every edge once, reading the previous round's
// distances, so after r rounds dist[v] is the shortest path that uses at most r edges.
// Negative weights are fine. Pass maxEdges = k + 1 for "at most k stops".
export function bellmanFord(n, edges, source, maxEdges = n - 1) {
  let dist = new Array(n).fill(Infinity);
  dist[source] = 0;
  for (let round = 1; round <= maxEdges; round++) {
    const next = dist.slice();            // read from dist, write into next
    let changed = false;
    for (const [u, v, w] of edges) {
      if (dist[u] + w < next[v]) {        // Infinity + w stays Infinity, so unreached nodes relax nothing
        next[v] = dist[u] + w;
        changed = true;
      }
    }
    dist = next;
    if (!changed) break;                  // nothing improved, so later rounds can't either
  }
  return dist;
}

// After n - 1 rounds every shortest path is final. If an edge can still be relaxed,
// a negative cycle is reachable and "shortest" is undefined.
export function hasNegativeCycle(n, edges, source) {
  const dist = bellmanFord(n, edges, source);
  return edges.some(([u, v, w]) => dist[u] + w < dist[v]);
}