Dijkstra's Algorithm

預備知識

Graph
Heap

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

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

白話理解

就像 Google 地圖規劃路線：從起點出發，每次都先確認「目前為止走過最短的那一站」，接著看看從這一站出發能不能讓其他還沒定案的地點變得更快抵達，一站一站往外擴散確認，直到所有地點的最短距離都確定為止。

使用限制

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

解析

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

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

步驟

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

逐步拆解：用一個小範例走一次流程

假設有 4 個城市 A、B、C、D，道路都是單行道（權重代表開車時間，單位：分鐘）如下：

A --1--> B
A --4--> C
B --2--> C
B --5--> D
C --1--> D

目標：從 A 走到 D 最短要多久？

步驟	拜訪的中繼站	distances 更新內容	說明
初始化	-	A=0, B=∞, C=∞, D=∞	除了起點 A 是 0，其他都先當作無限遠
1	A（目前最近，距離 0）	B=0+1=1, C=0+4=4	從 A 出發，更新它的鄰居 B、C
2	B（目前最近，距離 1）	C=min(4, 1+2)=3, D=1+5=6	發現「經過 B 到 C」只要 3 分鐘，比原本記錄的 4 分鐘更短，更新它！ D 暫時記錄為 6
3	C（目前最近，距離 3）	D=min(6, 3+1)=4	發現「經過 C 到 D」只要 4 分鐘，比原本記錄的 6 分鐘更短，再次更新
4	D（目前最近，距離 4）	-	走到終點，結束。最短距離為 4 分鐘，路徑是 A → B → C → D

可以看到，Dijkstra 之所以正確，關鍵就在每次拜訪到一個城市的鄰居時，都會檢查「有沒有更短的路徑」，發現更短就立刻覆蓋掉舊紀錄（第 2、3 步都發生了這件事），而不是走過一次就再也不管它。

實作

Python
JavaScript
Java

import heapq

class WeightedGraph:
    def __init__(self):
        self.adjacency_list = {}

    def add_vertex(self, vertex):
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []

    def add_edge(self, v1, v2, weight):
        self.adjacency_list[v1].append({"node": v2, "weight": weight})
        self.adjacency_list[v2].append({"node": v1, "weight": weight})

    # ... 其他 method

    def dijkstra(self, start, end):
        if not start or not end:
            return None
        pq = []  # 用 heapq 實作優先佇列，元素為 (distance, node)

        distances = {}
        previous = {}
        for node in self.adjacency_list:  # 遍歷所有的 Node
            if node == start:
                distances[node] = 0
                heapq.heappush(pq, (0, node))
            else:
                distances[node] = float("inf")
                heapq.heappush(pq, (float("inf"), node))
            previous[node] = None

        path = []
        while pq:
            distance, smallest = heapq.heappop(pq)

            if smallest == end:  # 走到終點，結束運算
                # 記錄 path 以便在最後 return
                while previous[smallest]:
                    path.append(smallest)
                    smallest = previous[smallest]
                break

            if smallest or distance != float("inf"):
                for neighbor in self.adjacency_list[smallest]:
                    next_neighbor = neighbor["node"]
                    new_distance = distances[smallest] + neighbor["weight"]
                    if new_distance < distances[next_neighbor]:
                        distances[next_neighbor] = new_distance
                        previous[next_neighbor] = smallest
                        heapq.heappush(pq, (new_distance, next_neighbor))

        path.append(smallest)
        path.reverse()
        return path

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();
  }
}

import java.util.*;

class WeightedGraph {
    private Map<String, List<Neighbor>> adjacencyList = new HashMap<>();

    static class Neighbor {
        String node;
        int weight;

        Neighbor(String node, int weight) {
            this.node = node;
            this.weight = weight;
        }
    }

    void addVertex(String vertex) {
        adjacencyList.putIfAbsent(vertex, new ArrayList<>());
    }

    void addEdge(String v1, String v2, int weight) {
        adjacencyList.get(v1).add(new Neighbor(v2, weight));
        adjacencyList.get(v2).add(new Neighbor(v1, weight));
    }

    // ... 其他 method

    List<String> dijkstra(String start, String end) {
        if (start == null || end == null) return null;
        // 用 PriorityQueue 實作優先佇列，元素為 [distance, node]
        PriorityQueue<Object[]> pq = new PriorityQueue<>(Comparator.comparingDouble(entry -> (double) entry[0]));

        Map<String, Double> distances = new HashMap<>();
        Map<String, String> previous = new HashMap<>();
        for (String node : adjacencyList.keySet()) { // 遍歷所有的 Node
            if (node.equals(start)) {
                distances.put(node, 0.0);
                pq.offer(new Object[]{0.0, node});
            } else {
                distances.put(node, Double.POSITIVE_INFINITY);
                pq.offer(new Object[]{Double.POSITIVE_INFINITY, node});
            }
            previous.put(node, null);
        }

        List<String> path = new ArrayList<>();
        String smallest = null;
        while (!pq.isEmpty()) {
            Object[] top = pq.poll();
            double distance = (double) top[0];
            smallest = (String) top[1];

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

            if (smallest != null || distances.get(smallest) != Double.POSITIVE_INFINITY) {
                for (Neighbor neighbor : adjacencyList.get(smallest)) {
                    String nextNeighbor = neighbor.node;
                    double newDistance = distances.get(smallest) + neighbor.weight;
                    if (newDistance < distances.get(nextNeighbor)) {
                        distances.put(nextNeighbor, newDistance);
                        previous.put(nextNeighbor, smallest);
                        pq.offer(new Object[]{newDistance, nextNeighbor});
                    }
                }
            }
        }

        path.add(smallest);
        Collections.reverse(path);
        return path;
    }
}

要素整理

Priority Queue：裝著準備要去的地點，排隊順序完全看「誰離起點最近（Distance）」
距離登記（Hash Map）：用來即時記錄「起點到各個頂點的最短總距離」
路線備忘（Hash Map）：（選配）
- 適用於要輸出整條路線的情況
- 這個 Map 用來記錄「每個點的前一站是誰」
- 演算法結束後，只要從終點「倒著看」這張表，就能完整還原出整條最短路線

複雜度

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

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

適用情況

導航與路線規劃：例如 Google 地圖從你目前位置到某個景點的最短開車時間。
網路路由：路由器之間計算封包傳輸的最短路徑。
物流與配送規劃：從倉庫出發，計算送到各個地點的最短距離或最少時間。
遊戲中的 AI 尋路：角色從目前位置移動到目標點，且地圖上不同地形有不同的移動成本（權重）。

常見誤區

以為 Dijkstra 可以處理負權重：只要圖裡有一條負權重的邊，Dijkstra 的「貪婪選最近點」邏輯就可能出錯（因為已經確定的最短距離，之後可能被一條負權重的路徑推翻），這時要改用 Bellman-Ford Algorithm。
忘記處理「已經拜訪過的點」：如果同一個點被重複從 Priority Queue 中拿出來處理，會做重複且無意義的運算，通常會搭配一個 visited 集合，或是在拿出節點時檢查它的距離是否早已被更新過（過期資料直接跳過）。
誤以為 BFS 也能找出帶權重圖的最短路徑：BFS（可參考 Graph Traversal）只保證在「每條邊權重都相同」的情況下找到最短路徑（用邊的「數量」當距離）；一旦邊有不同的權重，就必須用 Dijkstra 這類考慮權重大小的演算法。

解析​

步驟​

逐步拆解：用一個小範例走一次流程​

實作​

複雜度​

適用情況​

常見誤區​

解析

步驟

逐步拆解：用一個小範例走一次流程

實作

複雜度

適用情況

常見誤區