最短路徑 (Shortest Path)#

問題分類#

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 java.util.PriorityQueue

// graph[u] 存 (鄰居 v, 邊權 weight) 的清單
fun dijkstra(graph: Array<List<Pair<Int, Int>>>, start: Int, end: Int): Pair<Int, List<Int>> {
    val n = graph.size
    val dist = IntArray(n) { Int.MAX_VALUE }
    dist[start] = 0
    val prev = IntArray(n) { -1 }

    // (距離, 頂點)，以距離為序的小頂堆
    val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.first })
    pq.add(0 to start)

    while (pq.isNotEmpty()) {
        val (d, u) = pq.poll()

        if (u == end) break

        if (d > dist[u]) continue  // 已有更短路徑

        for ((v, weight) in graph[u]) {
            val newDist = dist[u] + weight  // dist[u] 已確定為有限值，不會溢位
            if (newDist < dist[v]) {
                dist[v] = newDist
                prev[v] = u
                pq.add(newDist to v)
            }
        }
    }

    return dist[end] to reconstructPath(prev, end)
}

private fun reconstructPath(prev: IntArray, end: Int): List<Int> {
    val path = mutableListOf<Int>()
    var node = end
    while (node != -1) {
        path.add(node)
        node = prev[node]
    }
    return path.reversed()
}

複雜度#

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

地圖導航最佳化#

問題#

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

最佳化策略#

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

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

不同最優目標#

無權圖的最短路徑#

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

fun bfsShortestPath(graph: Array<List<Int>>, start: Int, end: Int): Int {
    val queue = ArrayDeque<Pair<Int, Int>>()
    queue.add(start to 0)
    val visited = hashSetOf(start)

    while (queue.isNotEmpty()) {
        val (node, dist) = queue.removeFirst()

        if (node == end) return dist

        for (neighbor in graph[node]) {
            if (neighbor !in visited) {
                visited.add(neighbor)
                queue.add(neighbor to (dist + 1))
            }
        }
    }

    return -1  // 不可達
}

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

演算法比較#

換個視角：Dijkstra 其實是動態規劃#

前面把 Dijkstra 講成「貪心」：每一步都挑當前距離最小的未確定節點。這個說法沒錯，但只看到一半。換個更高的視角，Dijkstra 其實在做一件很「動態規劃」的事——它把「起點到終點的全程最短路徑」這個大問題，分解成一個個「起點到中間某點的最短路徑」子問題，然後從近到遠、逐步推進：每確定一個節點的最短距離，就等於解掉了一個子問題，再用它去推進更遠的節點。

這正是動態規劃的精神——最優子結構：大問題的最優解，是由子問題的最優解組合而成的。

最短路徑的子段也是最短路徑。 假設起點 $s$ 到終點 $t$ 的最短路徑經過中間點 $u$，那麼這條路徑中「$s$ 到 $u$」的那一段，也必定是 $s$ 到 $u$ 的最短路徑。若不然，就能找到一條更短的「$s$ 到 $u$」去替換它，拼回去會得到一條比原本更短的「$s$ 到 $t$」路徑——與「原本已是最短」矛盾。這個反證，是理解最優子結構最乾淨的例子。

正因為有這個性質，貪心與 DP 兩種視角在這裡是相通的：

Dijkstra 那個貪心選擇之所以正確，靠的就是最優子結構：當你取出當前距離最小的節點時，因為邊權非負，沒有任何尚未確定的路徑能繞遠路再回頭把它變得更短——所以這個節點的距離已經是最終答案，可以放心拿去推進別人。貪心的「敢於拍板」，背後是 DP 的最優子結構在撐腰。

能看穿「貪心」與「DP」在這裡是同一件事的兩種說法，正是演算法思維總綱裡強調的——看出不同描述、不同問題之間的等價性。

更廣的連結：很多 DP 問題本質是「圖上的最佳路徑」#

上一節說「Dijkstra 是 DP」；反過來看也成立——許多動態規劃問題，本質上就是在一張圖上找最短／最佳路徑。

訣竅是把問題「翻譯」成圖：

• 把問題的每個狀態當成圖的一個節點；
• 把每一次狀態轉移當成一條邊（轉移的代價就是邊權）；
• 求最優解，就等於在這張圖上找一條從「初始狀態」到「目標狀態」的最短／最佳路徑。

這類圖通常是分層的 DAG（有向無環圖）：狀態按「階段」排成一層層，邊只從前一層指向後一層，不會回頭，所以無環。沿著拓撲順序一層層推進，就是我們熟悉的 DP 填表過程。

經典例子是編輯距離：把「字串 A 的前 $i$ 個字元、字串 B 的前 $j$ 個字元」當成一個狀態 $(i, j)$，攤開來就是一張網格圖；插入、刪除、替換三種操作分別對應網格上往右、往下、往斜下的三條邊。求最小編輯距離，就是在這張網格圖上找一條從左上角到右下角、總權重最小的路徑。詳見動態規劃。

把這個觀點和上一節接起來，最短路徑與動態規劃其實是同一套思想的兩面：狀態即節點，轉移即邊，最優解即最佳路徑。 下次遇到一個看似全新的 DP 題，不妨先問自己：「它的狀態圖長什麼樣？」