跳至主要内容

Dijkstra's Algorithm

預備知識

Dijkstra's Algorithm 是用來尋找 Graph 的兩個點之間最短路徑的演算法。

簡單來說，它可以算出在一個有權重的圖 (Weighted Graph) 中，從某一個起點出發，到達其他所有頂點的最短距離是多少。這就像在 Google 地圖上設定好起點後，它能瞬間算出開車到各個景點最快要多久。

使用限制
  • 邊的權重必須全部都是正數（≥ 0）
  • 如果圖裡面有「負數」的權重（例如走這條路不花時間，反而能賺取時間），Dijkstra 就會失效。這時候必須改用 Bellman-Ford 演算法。

解析​

Dijkstra 的核心思維是貪婪法 (Greedy)。

非常像在走迷宮時的直覺：「每一次，都選擇目前看起來離起點最近、且還沒拜訪過的點來前進。」

步驟​

  1. 應用於具有權重的 Graph，即 Weighted Graph
  2. 初始化
    • 設定好起點與終點
    • 一開始，除了起點到自己的距離是 0 以外，到其他所有點的距離都先假設是無限遠（Infinity）
  3. 挑選下一站
    • 每次都從 「還沒去過的地方」 裡，挑選一個當前離起點最近的點作為中繼站
    • 可以用 Priority Queue（通常用 Heap 實作），會自動把距離最短的點排在最前面，方便直接拿取
  4. 探訪鄰居
    • 到達這個中繼站（當前的點），再去查看所有跟它直接相連的鄰居
  5. 計算新路徑
    • 計算「從起點走到中繼站，再從中繼站走到鄰居」的總距離是多少。
  6. 更新紀錄
    • 如果發現這次算出來的總距離，比之前記錄的還要短，就更新紀錄，填入更短的新距離

實作​

class WeightedGraph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }

  addEdge(v1, v2, weight) {
    this.adjacencyList[v1].push({ node: v2, weight });
    this.adjacencyList[v2].push({ node: v1, weight });
  }
  
  ... // 其他 method
  
  dijkstra(start, end) {
    if (!start || !end) return undefined;
    const pq = new Heap();     
    // 假設已經有個定義好的 Heap 可直接用
    // 儲存資料時定義新的 Node，帶有 val 與 priority 兩個性質
    
    const distances = {};
    const previous = {};
    for (let node in this.adjacencyList) {  // 遍歷所有的 Node
      if (node === start) {
        distances[node] = 0;
        pq.insert(node, 0);
      } else {
        distances[node] = Infinity;
        pq.insert(node, Infinity);
      }
      previous[node] = null;
    }
    
    const path = [];
    while (pq.values.length) {
      const smallest = pq.remove().val;

      if (smallest === end) { // 走到終點，結束運算
        // 記錄 path 以便在最後 return
        while (previous[smallest]) {
          path.push(smallest);
          smallest = previous[smallest];
        }
        break;
      }

      if (smallest || distances[smallest] !== Infinity) {
        this.adjacencyList[smallest].forEach((neighbor) => {
          const nextNeighbor = neighbor.node;
          const newDistance = distances[smallest] + neighbor.weight;
          if (newDistance < distances[nextNeighbor]) {
            distances[nextNeighbor] = newDistance;
            previous[nextNeighbor] = smallest;
            pq.insert(nextNeighbor, newDistance);
          }
        });
      }
    }
    return path.concat(smallest).reverse();
  }
}
要素整理
  • Priority Queue：裝著準備要去的地點，排隊順序完全看「誰離起點最近（Distance）」
  • 距離登記（Hash Map）：用來即時記錄「起點到各個頂點的最短總距離」
  • 路線備忘（Hash Map）：（選配）
    • 適用於要輸出整條路線的情況
    • 這個 Map 用來記錄「每個點的前一站是誰」
    • 演算法結束後，只要從終點「倒著看」這張表，就能完整還原出整條最短路線

Dijkstra 的複雜度​

時間複雜度取決於「如何找出下一個最近的點」：

  1. 使用一般 Array 線性搜尋
    • 時間複雜度：O(V^2)
    • 原因：每次要找最近的點，都要把所有頂點（V）掃描一遍，總共要找 V 次。
  2. 使用 Min-Heap 優化
    • 時間複雜度：O((V + E) log V)， 勝出 🏆
    • 原因：把找最近點的時間降到了 O(log V)。這是目前程式實作上最推薦且最常用的標準做法。
  3. 空間複雜度
    • O(V + E)。需要儲存 Graph、Heap 以及記錄距離的 Hash Map。
最後於 更新