05 — Graph Shortest Paths

Algorithm Comparison

---

Dijkstra's Algorithm

Shortest path from single source, no negative edges.

function dijkstra(adj: [number, number][][], n: number, src: number): number[] {
  const dist = new Array(n).fill(Infinity);
  dist[src] = 0;
  
  // Min-heap: [distance, node]
  const pq: [number, number][] = [[0, src]];
  
  while (pq.length > 0) {
    // Extract min (simple version — use proper min-heap in production)
    pq.sort((a, b) => a[0] - b[0]);
    const [d, u] = pq.shift()!;
    
    if (d > dist[u]) continue; // Stale entry
    
    for (const [v, w] of adj[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        pq.push([dist[v], v]);
      }
    }
  }
  return dist;
}

Example: Find shortest path from A to all nodes

    A ---2--- B ---1--- D
    |         |         |
    4         3         2
    |         |         |
    C ---1--- E ---5--- F

dist[A]=0, dist[B]=2, dist[C]=4, dist[D]=3, dist[E]=5, dist[F]=5

---

Bellman-Ford

Works with negative edges. Detects negative cycles.

function bellmanFord(edges: [number, number, number][], n: number, src: number): number[] | null {
  const dist = new Array(n).fill(Infinity);
  dist[src] = 0;
  
  // Relax all edges (n-1) times
  for (let i = 0; i < n - 1; i++) {
    for (const [u, v, w] of edges) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
      }
    }
  }
  
  // Check for negative cycle (n-th relaxation)
  for (const [u, v, w] of edges) {
    if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
      return null; // Negative cycle detected
    }
  }
  
  return dist;
}

---

Floyd-Warshall

All-pairs shortest path. O(V³).

function floydWarshall(adj: number[][]): number[][] {
  const n = adj.length;
  const dist = adj.map(row => [...row]); // Clone
  
  // dist[i][j] = direct edge weight, Infinity if no edge, 0 if i===j
  
  for (let k = 0; k < n; k++) {         // Intermediate node
    for (let i = 0; i < n; i++) {       // Source
      for (let j = 0; j < n; j++) {     // Destination
        if (dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }
  return dist;
}

---

0-1 BFS

Graph with edge weights 0 or 1 only. Uses deque instead of priority queue.

function bfs01(adj: [number, number][][], n: number, src: number): number[] {
  const dist = new Array(n).fill(Infinity);
  dist[src] = 0;
  const deque: number[] = [src];
  
  while (deque.length > 0) {
    const u = deque.shift()!;
    
    for (const [v, w] of adj[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        if (w === 0) deque.unshift(v);  // Weight 0 → front
        else deque.push(v);              // Weight 1 → back
      }
    }
  }
  return dist;
}

---

Path Reconstruction

function dijkstraWithPath(adj: [number, number][][], n: number, src: number, dest: number): number[] {
  const dist = new Array(n).fill(Infinity);
  const parent = new Array(n).fill(-1);
  dist[src] = 0;
  const pq: [number, number][] = [[0, src]];
  
  while (pq.length) {
    pq.sort((a, b) => a[0] - b[0]);
    const [d, u] = pq.shift()!;
    if (d > dist[u]) continue;
    
    for (const [v, w] of adj[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        parent[v] = u;
        pq.push([dist[v], v]);
      }
    }
  }
  
  // Reconstruct path
  const path: number[] = [];
  for (let node = dest; node !== -1; node = parent[node]) {
    path.unshift(node);
  }
  return path[0] === src ? path : []; // Empty if unreachable
}

---

When to Use Which

---

Key Takeaways

• Dijkstra = greedy + min-heap; fails with negative edges
• Bellman-Ford = relax all edges V-1 times; detects negative cycles on V-th pass
• Floyd-Warshall = try every intermediate node; O(V³) for all pairs
• 0-1 BFS = O(V+E) using deque; push weight-0 to front, weight-1 to back
• Store parent array during shortest path to reconstruct the actual path