最短路徑演算法 — Dijkstra、Bellman-Ford、Floyd-Warshall 完整比較 | 資料結構與演算法

type Edge = [number, number]; // [neighbor, weight]
type Graph = Map<number, Edge[]>;

class MinHeap {
  private heap: [number, number][] = []; // [dist, node]

  push(item: [number, number]): void {
    this.heap.push(item);
    this.siftUp(this.heap.length - 1);
  }

  pop(): [number, number] | undefined {
    if (this.heap.length === 0) return undefined;
    const top = this.heap[0];
    const last = this.heap.pop()!;
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.siftDown(0);
    }
    return top;
  }

  get size(): number {
    return this.heap.length;
  }

  private siftUp(i: number): void {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.heap[parent][0] > this.heap[i][0]) {
        [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
        i = parent;
      } else break;
    }
  }

  private siftDown(i: number): void {
    const n = this.heap.length;
    while (true) {
      let smallest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      if (left < n && this.heap[left][0] < this.heap[smallest][0]) smallest = left;
      if (right < n && this.heap[right][0] < this.heap[smallest][0]) smallest = right;
      if (smallest === i) break;
      [this.heap[smallest], this.heap[i]] = [this.heap[i], this.heap[smallest]];
      i = smallest;
    }
  }
}

function dijkstra(graph: Graph, n: number, src: number): number[] {
  const dist = new Array(n + 1).fill(Infinity);
  dist[src] = 0;
  const heap = new MinHeap();
  heap.push([0, src]);

  while (heap.size > 0) {
    const [d, u] = heap.pop()!;
    // Lazy Deletion：若已找到更短路徑則跳過
    if (d > dist[u]) continue;

    for (const [v, w] of (graph.get(u) ?? [])) {
      const newDist = dist[u] + w;
      if (newDist < dist[v]) {
        dist[v] = newDist;
        heap.push([newDist, v]);
      }
    }
  }

  return dist;
}

interface WeightedEdge {
  from: number;
  to: number;
  weight: number;
}

interface BellmanFordResult {
  dist: number[];
  hasNegativeCycle: boolean;
}

function bellmanFord(
  edges: WeightedEdge[],
  n: number,
  src: number
): BellmanFordResult {
  const dist = new Array(n + 1).fill(Infinity);
  dist[src] = 0;

  // 鬆弛 V-1 次，保證最短路徑最多含 V-1 條邊
  for (let i = 0; i < n - 1; i++) {
    let updated = false;
    for (const { from, to, weight } of edges) {
      if (dist[from] !== Infinity && dist[from] + weight < dist[to]) {
        dist[to] = dist[from] + weight;
        updated = true;
      }
    }
    // 提前終止優化：若無更新則已收斂
    if (!updated) break;
  }

  // 第 V 次鬆弛若仍有更新 → 存在負環
  let hasNegativeCycle = false;
  for (const { from, to, weight } of edges) {
    if (dist[from] !== Infinity && dist[from] + weight < dist[to]) {
      hasNegativeCycle = true;
      break;
    }
  }

  return { dist, hasNegativeCycle };
}

function floydWarshall(n: number, edges: [number, number, number][]): number[][] {
  // dist[i][j] = 節點 i 到節點 j 的最短距離
  const INF = Infinity;
  const dist: number[][] = Array.from({ length: n }, (_, i) =>
    Array.from({ length: n }, (_, j) => (i === j ? 0 : INF))
  );

  // 初始化直接邊
  for (const [u, v, w] of edges) {
    dist[u][v] = Math.min(dist[u][v], w);
  }

  // 中繼節點 k：嘗試「經由 k 中轉」是否能縮短 i→j 路徑
  // 注意：k 必須在最外層！
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (dist[i][k] !== INF && dist[k][j] !== INF) {
          dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
        }
      }
    }
  }

  // 負環偵測：若 dist[i][i] < 0，則存在負環
  for (let i = 0; i < n; i++) {
    if (dist[i][i] < 0) {
      throw new Error(`Negative cycle detected involving node ${i}`);
    }
  }

  return dist;
}

interface Point {
  row: number;
  col: number;
}

// Manhattan Distance：適用於網格，禁止對角移動時的最優啟發函數
function manhattan(a: Point, b: Point): number {
  return Math.abs(a.row - b.row) + Math.abs(a.col - b.col);
}

function aStar(
  grid: number[][],
  start: Point,
  end: Point
): number {
  const rows = grid.length;
  const cols = grid[0].length;
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];

  // g[r][c] = 從起點到 (r,c) 的實際最短距離
  const g: number[][] = Array.from({ length: rows }, () =>
    new Array(cols).fill(Infinity)
  );
  g[start.row][start.col] = 0;

  // f = g + h，Min-Heap 以 f 值排序 [f, gCost, row, col]
  const heap: [number, number, number, number][] = [];
  const pushHeap = (item: [number, number, number, number]) => {
    heap.push(item);
    heap.sort((a, b) => a[0] - b[0]); // 簡化版，大規模應用請改用完整 MinHeap
  };
  pushHeap([manhattan(start, end), 0, start.row, start.col]);

  while (heap.length > 0) {
    const [, gCost, r, c] = heap.shift()!;
    if (r === end.row && c === end.col) return gCost;
    if (gCost > g[r][c]) continue; // Lazy Deletion

    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (grid[nr][nc] === 1) continue; // 障礙物

      const newG = g[r][c] + 1;
      if (newG < g[nr][nc]) {
        g[nr][nc] = newG;
        const h = manhattan({ row: nr, col: nc }, end);
        pushHeap([newG + h, newG, nr, nc]);
      }
    }
  }

  return -1; // 不可達
}

#include <vector>
#include <queue>
#include <climits>
using namespace std;

using Edge = pair<int, int>; // {鄰居節點, 邊權重}
using PII  = pair<int, int>; // {距離, 節點}

vector<int> dijkstra(int n, vector<vector<Edge>>& graph, int src) {
    vector<int> dist(n + 1, INT_MAX);
    dist[src] = 0;

    // Min-Heap：以 greater<PII> 使小的元素優先
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue; // Lazy Deletion

        for (auto [v, w] : graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

#include <vector>
#include <climits>
using namespace std;

struct WeightedEdge { int from, to, weight; };

pair<vector<int>, bool> bellmanFord(
    int n,
    const vector<WeightedEdge>& edges,
    int src
) {
    vector<int> dist(n + 1, INT_MAX);
    dist[src] = 0;

    for (int i = 0; i < n - 1; i++) {
        bool updated = false;
        for (const auto& [from, to, w] : edges) {
            if (dist[from] != INT_MAX && dist[from] + w < dist[to]) {
                dist[to] = dist[from] + w;
                updated = true;
            }
        }
        if (!updated) break; // 提前終止
    }

    bool negCycle = false;
    for (const auto& [from, to, w] : edges) {
        if (dist[from] != INT_MAX && dist[from] + w < dist[to]) {
            negCycle = true;
            break;
        }
    }
    return {dist, negCycle};
}

#include <vector>
using namespace std;

vector<vector<long long>> floydWarshall(int n, vector<tuple<int,int,int>>& edges) {
    const long long INF = 1e18;
    vector<vector<long long>> dist(n, vector<long long>(n, INF));
    for (int i = 0; i < n; i++) dist[i][i] = 0;
    for (auto [u, v, w] : edges) dist[u][v] = min(dist[u][v], (long long)w);

    // k 在最外層是關鍵！
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dist[i][k] < INF && dist[k][j] < INF)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    return dist;
}

// 0-1 BFS：邊權為 0 的節點從前端插入，邊權為 1 的從後端插入
function zeroOneBFS(
  graph: { to: number; weight: 0 | 1 }[][],
  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 { to: v, weight: w } of graph[u]) {
      const newDist = dist[u] + w;
      if (newDist < dist[v]) {
        dist[v] = newDist;
        if (w === 0) deque.unshift(v); // 零權邊 → 從前端插入
        else deque.push(v);             // 一權邊 → 從後端插入
      }
    }
  }

  return dist;
}

// 多源最短路：新增虛擬節點 superSrc（索引 n），連接所有真實起點
// graph 節點為 0..n-1，超級起點為 n
function multiSourceDijkstra(
  graph: Map<number, [number, number][]>,
  n: number,
  sources: number[]
): number[] {
  const superSrc = n;
  graph.set(superSrc, sources.map(src => [src, 0])); // 零權邊
  const dist = dijkstra(graph, n + 1, superSrc);
  return dist.slice(0, n); // 去掉超級起點本身的距離
}

// 思路：Dijkstra 從 k 出發，取所有節點最短距離的最大值
// 時間：O((V+E) log V)，空間：O(V+E)

function networkDelayTime(times: number[][], n: number, k: number): number {
  // 建圖
  const graph = new Map<number, [number, number][]>();
  for (let i = 1; i <= n; i++) graph.set(i, []);
  for (const [u, v, w] of times) graph.get(u)!.push([v, w]);

  // Dijkstra（簡化版 heap，面試可用）
  const dist = new Array(n + 1).fill(Infinity);
  dist[k] = 0;
  const heap: [number, number][] = [[0, k]];

  while (heap.length > 0) {
    heap.sort((a, b) => a[0] - b[0]);
    const [d, u] = heap.shift()!;
    if (d > dist[u]) continue;
    for (const [v, w] of graph.get(u)!) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        heap.push([dist[v], v]);
      }
    }
  }

  const ans = Math.max(...dist.slice(1));
  return ans === Infinity ? -1 : ans;
}
// 測試：times=[[2,1,1],[2,3,1],[3,4,1]], n=4, k=2 → 2

// 思路：Bellman-Ford 只做 k+1 次鬆弛，每次代表多走一條邊
// 關鍵：每輪必須用上一輪的 dist 副本，避免同輪連鎖更新！
// 時間：O(k * E)，空間：O(n)

function findCheapestPrice(
  n: number,
  flights: number[][],
  src: number,
  dst: number,
  k: number
): number {
  let dist = new Array(n).fill(Infinity);
  dist[src] = 0;

  for (let i = 0; i <= k; i++) {
    // 複製本輪 dist，避免在同一輪內連鎖更新
    const temp = [...dist];
    for (const [from, to, price] of flights) {
      if (dist[from] !== Infinity && dist[from] + price < temp[to]) {
        temp[to] = dist[from] + price;
      }
    }
    dist = temp;
  }

  return dist[dst] === Infinity ? -1 : dist[dst];
}
// 測試：n=4, flights=[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]]
//       src=0, dst=3, k=1 → 700

// 思路：Floyd-Warshall 建全源最短路矩陣，再統計每個城市的鄰居數
// 時間：O(V³)，空間：O(V²)

function findTheCity(
  n: number,
  edges: number[][],
  distanceThreshold: number
): number {
  const INF = Infinity;
  const dist: number[][] = Array.from({ length: n }, (_, i) =>
    Array.from({ length: n }, (_, j) => (i === j ? 0 : INF))
  );

  for (const [u, v, w] of edges) {
    dist[u][v] = w;
    dist[v][u] = w; // 無向圖
  }

  // Floyd-Warshall（k 在最外層）
  for (let k = 0; k < n; k++)
    for (let i = 0; i < n; i++)
      for (let j = 0; j < n; j++)
        if (dist[i][k] !== INF && dist[k][j] !== INF)
          dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);

  // 統計每個城市閾值內的鄰居數，取鄰居最少且編號最大的
  let result = -1;
  let minNeighbors = Infinity;

  for (let i = 0; i < n; i++) {
    let count = 0;
    for (let j = 0; j < n; j++) {
      if (i !== j && dist[i][j] <= distanceThreshold) count++;
    }
    // 並列時取編號最大（>=），即 i 較大時也更新
    if (count <= minNeighbors) {
      minNeighbors = count;
      result = i;
    }
  }

  return result;
}
// 測試：n=4, edges=[[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold=4 → 3

// 思路：Dijkstra 的邊權 = 路徑上的最大格子值（瓶頸最小化）
// dist[r][c] = 到達 (r,c) 的最小最大高度
// 時間：O(n² log n)，空間：O(n²)

function swimInWater(grid: number[][]): number {
  const n = grid.length;
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
  const dist: number[][] = Array.from({ length: n }, () =>
    new Array(n).fill(Infinity)
  );
  dist[0][0] = grid[0][0];

  // [最大高度, row, col]
  const heap: [number, number, number][] = [[grid[0][0], 0, 0]];

  while (heap.length > 0) {
    heap.sort((a, b) => a[0] - b[0]);
    const [cost, r, c] = heap.shift()!;
    if (r === n - 1 && c === n - 1) return cost;
    if (cost > dist[r][c]) continue;

    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;
      if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;

      // 瓶頸：整段路徑的最大高度 = max(已知最大高度, 下一格高度)
      const newCost = Math.max(dist[r][c], grid[nr][nc]);
      if (newCost < dist[nr][nc]) {
        dist[nr][nc] = newCost;
        heap.push([newCost, nr, nc]);
      }
    }
  }

  return dist[n-1][n-1];
}
// 測試：grid=[[0,2],[1,3]] → 3

// 思路：Dijkstra 變體，dist[r][c] = 到達 (r,c) 的最小努力值（最大高度差）
// 時間：O(V log V)，V = rows * cols，空間：O(V)

function minimumEffortPath(heights: number[][]): number {
  const rows = heights.length;
  const cols = heights[0].length;
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
  const dist: number[][] = Array.from({ length: rows }, () =>
    new Array(cols).fill(Infinity)
  );
  dist[0][0] = 0;

  const heap: [number, number, number][] = [[0, 0, 0]]; // [effort, row, col]

  while (heap.length > 0) {
    heap.sort((a, b) => a[0] - b[0]);
    const [effort, r, c] = heap.shift()!;
    if (r === rows - 1 && c === cols - 1) return effort;
    if (effort > dist[r][c]) continue;

    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;

      // 本段努力值 = 高度差；整段路徑努力值 = 歷史最大值 vs 本段
      const segEffort = Math.abs(heights[nr][nc] - heights[r][c]);
      const newEffort = Math.max(dist[r][c], segEffort);

      if (newEffort < dist[nr][nc]) {
        dist[nr][nc] = newEffort;
        heap.push([newEffort, nr, nc]);
      }
    }
  }

  return 0;
}
// 測試：heights=[[1,2,2],[3,8,2],[5,3,5]] → 2