題目描述:有 n 個城市和 m 條單向航班。每條航班有起點、終點和費用。給定起點 src、終點 dst,以及最多可停靠 k 個中間站(即最多搭乘 k+1 段航班),求從 src 到 dst 的最低費用。若無法到達則回傳 -1。
解題思路:本題使用 Bellman-Ford 演算法的變形,限制鬆弛輪數為 k+1 輪(對應最多 k+1 段航班,即最多 k 個中間停靠站)。
核心技巧:每一輪鬆弛必須使用上一輪的距離陣列(而非當前輪的),否則一輪內可能使用多條邊,等同於走了超過一段路。具體做法是在每輪開始時複製當前 dist 陣列為 prev,所有鬆弛計算都以 prev 為基準。
演算法步驟:
dist 陣列為無窮大,dist[src] = 0。dist 為 prev。(u, v, w),若 prev[u] != INF,則嘗試更新 dist[v] = min(dist[v], prev[u] + w)。dist[dst] == INF 則回傳 -1,否則回傳 dist[dst]。時間複雜度 O(K × E),空間複雜度 O(V),非常高效。
時間複雜度:O(K × E) — 共進行 k+1 輪鬆弛,每輪遍歷所有 E 條邊,其中 E 為航班數量。
空間複雜度:O(V) — 僅使用兩個長度為 n 的距離陣列(dist 與 prev),V 為城市數量。
1. Initialize dist[0..n-1] = INF, dist[src] = 0.
2. Repeat (k+1) times:
a. prev = copy of dist // freeze current state
b. For each flight (u, v, w):
- If prev[u] != INF and prev[u] + w < dist[v]:
- dist[v] = prev[u] + w
3. If dist[dst] == INF, return -1.
4. Return dist[dst].Dijkstra + 停靠站計數 O((V + E) log V):在 Dijkstra 中,狀態為 (cost, node, stops_used),只要 stops_used ≤ k 就可以繼續擴展。用最小堆按 cost 排序。此方法在稀疏圖上更快,但需要注意同一節點可能以不同的停靠數抵達,不能直接用 visited 陣列剪枝,需允許更少停靠數的路徑重新入堆。
BFS(層次搜尋)O(K × E):等同於 Bellman-Ford 的直觀版本,每輪 BFS 相當於一段航班,共進行 k+1 輪,記錄每個節點的最低費用。邏輯與 Bellman-Ford 相同但以 BFS 佇列實作,可讀性更高。