最短路徑#

問題分類#

Dijkstra 演算法#

適用條件#

• 有向/無向有權圖
• 邊權必須非負

核心思想#

貪心策略：每次選擇距離起點最近的未處理頂點，更新其鄰居的距離。

演算法步驟#

flowchart TD
    A[1. 初始化<br/>起點=0, 其他=∞] --> B[2. 起點加入優先佇列]
    B --> C{3. 佇列為空?}
    C -->|否| D[取出距離最小的頂點 u]
    D --> E{是目標頂點?}
    E -->|是| F[返回結果]
    E -->|否| G[4. 遍歷 u 的鄰居 v]
    G --> H{"dist[u]+w < dist[v]?"}
    H -->|是| I["更新 dist[v]<br/>v 加入佇列"]
    H -->|否| J[跳過]
    I --> C
    J --> C
    C -->|是| K[無法到達]

    style F fill:#e8f5e9
    style K fill:#ffebee

1. 初始化：起點距離 = 0，其他 = ∞
2. 將起點加入優先佇列（小頂堆）
3. 取出距離最小的頂點 u
4. 對 u 的每個鄰居 v：
   • 若 dist[u] + weight(u,v) < dist[v]
   • 更新 dist[v]，將 v 加入佇列
5. 重複直到目標頂點出隊或佇列為空

import heapq

def dijkstra(graph, start, end):
    n = len(graph)
    dist = [float('inf')] * n
    dist[start] = 0
    prev = [-1] * n

    # (距離, 頂點)
    pq = [(0, start)]

    while pq:
        d, u = heapq.heappop(pq)

        if u == end:
            break

        if d > dist[u]:  # 已有更短路徑
            continue

        for v, weight in graph[u]:
            new_dist = dist[u] + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                prev[v] = u
                heapq.heappush(pq, (new_dist, v))

    return dist[end], reconstruct_path(prev, start, end)

def reconstruct_path(prev, start, end):
    path = []
    node = end
    while node != -1:
        path.append(node)
        node = prev[node]
    return path[::-1]

複雜度#

• 時間：O((V + E) log V)（使用堆）
• 空間：O(V)

地圖導航優化#

問題#

實際地圖有數億頂點，全圖 Dijkstra 太慢。

優化策略#

1. 區域限制：只在起終點附近的小區塊內搜尋
2. 分層導航：
   • 遠距離：先規劃城市級路線
   • 近距離：再細化街道級路線
3. 啟發式搜尋：A* 演算法（結合預估距離）

工程思維：不追求絕對最優，可行的次優解往往更實用。

不同最優目標#

無權圖的最短路徑#

對於邊權都為 1 的圖，BFS 保證找到最短路徑：

def bfs_shortest_path(graph, start, end):
    from collections import deque

    queue = deque([(start, 0)])
    visited = {start}

    while queue:
        node, dist = queue.popleft()

        if node == end:
            return dist

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))

    return -1  # 不可達

BFS 保證最短：第一次訪問到終點時的路徑長度一定是最短的（無權圖）。

演算法比較#