題目與適用情境
給定一張有向圖，共有 n 個節點，編號為 0 到 n - 1。每條邊用 (from, to, weight) 表示。給定 source 和 target，回傳從起點到終點的最短距離和 任意一條最短路徑；如果終點不可達，回傳 (-1, [])。
本題約定 1 <= n <= 100000、0 <= m <= 300000，節點編號都合法，且 0 <= weight <= 10^9。允許平行邊、零權重邊和自環；source、target 一定合法。 若起點就是終點，回傳 (0, [source])。存在多條等長最短路徑時，回傳任意一條即可。
例如，邊為 (0, 1, 4)、(0, 2, 1)、(2, 1, 2)、(1, 3, 1)、 (2, 3, 5)、(3, 4, 3)、(2, 4, 12) 時，從 0 到 4 的最短距離為 7， 路徑為 [0, 2, 1, 3, 4]。
「邊權重非負」是演算法合約的一部分。看到帶權圖不能立刻套用 Dijkstra：無權重或等權重圖 優先考慮 BFS；DAG 可以按拓撲順序做動態規劃；一般圖若含負權重邊，則要考慮 Bellman-Ford 等演算法。
面試官考察重點
第一，看能否從輸入合約選對演算法。這裡只有單源查詢，且所有邊權重非負，所以適合 Dijkstra。只說「帶權圖用 Dijkstra」，卻不確認負權重邊，就漏掉了最關鍵的前提。
第二，看能否把圖和候選距離維護好。節點最多 100000 個，鄰接矩陣需要 O(V^2) 空間， 不適合本題。鄰接串列只儲存實際存在的邊；最小堆負責取出目前已發現距離最小的未確定節點。
第三，看是否理解堆中的重複項目。Python 的 heapq 不支援直接修改任意項目的優先順序。 常見做法是在距離變小時推入新項目，舊項目之後出堆時，如果距離已經不等於 distances[node]，就把它當成過期項目跳過。這個惰性刪除細節會影響正確性說明和精確複雜度。
面試官還會追問證明：為什麼節點的目前項目第一次出堆後距離就確定了；為什麼非負邊權重能 保證這個貪心步驟；為什麼可以在終點出堆時結束，卻不能在第一次發現終點時結束。路徑還原、 不可達、零權重邊、平行邊、整數位元寬度和對抗測試也應主動涵蓋。
回答前需要釐清的問題
- 邊權重可能為負嗎？ 本題明確不會。若允許負權重邊，Dijkstra 的確定性證明和提前結束都不成立。
- 圖是有向圖嗎？ 是。無向圖需要把每條邊的兩個方向都加入鄰接串列。
- 只回傳距離，還是也要回傳路徑？ 本題兩者都要，所以每次嚴格改善距離時還要記錄前驅。
- 允許平行邊、零權重邊和自環嗎？ 允許。鬆弛操作可直接處理；非負自環不會改善目前節點。
- 不可達如何表示？ 回傳
(-1, [])，避免與起點等於終點的零距離混淆。 - 多條最短路徑如何選？ 任意一條即可。實作只在嚴格變小時更新前驅，等長路徑不會反覆改寫。
- 距離會不會溢位？ 簡單最短路徑至多包含
n - 1條邊，在本題限制下小於10^14。
Python 整數不會溢位；固定寬度整數語言應使用 64 位元型別。
30 秒回答框架
「我會先建立鄰接串列，用 distances[v] 表示目前找到的起點到 v 的最短距離。起點距離設為 0，並把 (0, source) 放進最小堆。每次彈出最小項目，如果它與陣列中的目前距離不一致， 代表已經過期，直接跳過；否則因為所有邊權重非負，這個節點的距離已經確定。接著鬆弛所有出邊， 每次嚴格改善都推入新項目並記錄前驅。終點的目前項目出堆時可以結束。若終點仍為無限大，回傳 (-1, [])；否則沿前驅反向還原路徑再翻轉。惰性重複項目的實作時間為 O((V + E) log E)，空間為 O(V + E)。」
分步深入解答
先區分「找到一條路」和「已經證明最短」。distances[v] 要麼是無限大，要麼是某條實際路徑的 長度，因此它是最短距離的上界，不會憑空小於真實答案。對邊 u -> v、權重 w 做鬆弛時， 判斷經過 u 的路徑是否更短：distances[u] + w < distances[v]。只有嚴格變小時才更新 距離和 previous[v]。
堆中允許同一節點出現多次。範例裡，邊 0 -> 1 會先推入距離 4；處理節點 2 後，路徑 0 -> 2 -> 1 又把節點 1 改善為距離 3，並推入第二個項目。之後 (4, 1) 出堆時， 4 != distances[1]，代表它已經過期，應直接跳過。不需要在堆裡尋找並刪除舊項目，也不需要 額外使用一個在入堆時就標記的 visited 集合。
from heapq import heappop, heappush
def shortest_path(
n: int,
edges: list[tuple[int, int, int]],
source: int,
target: int,
) -> tuple[int, list[int]]:
graph: list[list[tuple[int, int]]] = [[] for _ in range(n)]
for node, neighbor, weight in edges:
if weight < 0:
raise ValueError("Dijkstra requires non-negative edge weights")
graph[node].append((neighbor, weight))
distances = [float("inf")] * n
previous = [-1] * n
distances[source] = 0
heap: list[tuple[int, int]] = [(0, source)]
while heap:
distance, node = heappop(heap)
if distance != distances[node]:
continue
if node == target:
break
for neighbor, weight in graph[node]:
candidate = distance + weight
if candidate < distances[neighbor]:
distances[neighbor] = candidate
previous[neighbor] = node
heappush(heap, (candidate, neighbor))
if distances[target] == float("inf"):
return -1, []
path = []
node = target
while node != -1:
path.append(node)
node = previous[node]
path.reverse()
return int(distances[target]), path正確性可以分兩步證明。第一，每個有限的 distances 值都來自一條實際已發現路徑，所以不可能 低於真實最短距離。第二，假設節點 u 的目前項目出堆了，卻還存在一條更短路徑。在這條更短路徑 上找到第一個尚未確定的節點，其前驅記為 x。x 已經更早確定，因此它的出邊已經被鬆弛； 這個未確定節點會得到一個不大於那條假設路徑長度的堆鍵。因為其餘邊權重都非負，這個鍵嚴格小於 剛彈出的 u 的鍵，理應先出堆，產生矛盾。所以目前出堆距離一定已經是最短距離。
這個證明也確定了提前結束的位置：只能在終點以目前、未過期距離出堆後停止，不能在某條邊第一次 發現終點時停止。範例中節點 4 最早被發現的直接候選距離是 13，最終最短距離卻是 7。
每次 previous[v] = u 都記錄了目前最佳路徑的最後一條邊。終點距離確定後，沿前驅往回走一定 能到起點，因為每個前驅都來自一條真實的起點路徑。反向收集後再翻轉即可得到正向路徑。起點等於 終點時，起點第一次出堆就結束，還原結果自然是 [source]。
建立鄰接串列需要 O(E) 時間和 O(V + E) 空間。每次成功鬆弛最多新增一個堆項目，因此除起點 外最多有 E 次入堆。惰性重複項目會讓堆規模達到 O(E)，所以時間為 O((V + E) log E)，總空間為 O(V + E)。教科書中常見的 O((V + E) log V) 通常對應 支援 decrease-key 的堆，或對簡單稀疏圖做了常用簡化；面試時說明實作差異會更精確。
測試要涵蓋合約，不只是一條正常範例。上述範例應回傳 (7, [0, 2, 1, 3, 4])。平行邊和 零權重邊 (0, 1, 10)、(0, 1, 2)、(1, 2, 0) 應回傳 (2, [0, 1, 2])。 還要測試終點不可達、起終點相同、自環、等長候選路徑和零權重邊。負權重邊應觸發明確例外，不能在 演算法前提已被破壞時悄悄回傳一個結果。
還可以做小規模差分測試：隨機產生非負權重圖，對每個起點分別執行本函式和 Bellman-Ford，比較 所有距離。對回傳路徑，還要檢查首尾節點、每一對相鄰節點是否有對應輸入邊，並加總所選邊權重。 存在平行邊時，測試不能假定一對節點之間只有一條邊，必須比對實際採用的邊權重。
高品質示範回答
「我先確認所有邊權重非負、圖是有向圖，而且任意一條最短路徑都可以回傳。滿足這些條件後可以 使用 Dijkstra。節點最多 100000 個、邊最多 300000 條，所以我會使用鄰接串列；鄰接矩陣空間 太大。
distances[v] 初始都是無限大，只有起點為 0。最小堆儲存已經發現的 (distance, node)。 找到一條更短路徑時，我更新鄰居的距離和前驅，並推入新項目。由於 heapq 沒有任意項目的 decrease-key，舊項目會留在堆中；出堆距離若不等於陣列目前值，就代表過期，直接跳過。
核心是確定性不變量：當節點 u 的目前項目是堆頂時，任何假設中的更短路徑都會包含一個首個尚未 確定的節點，它的前驅已經確定並完成鬆弛。由於其餘邊權重非負，那個路徑前綴對應的堆鍵應該早於 u 出堆，矛盾。因此 u 的距離已經最終確定。這也說明可以在終點的目前項目出堆時結束，但不能 在第一次看到終點時結束。
若終點仍是無限大，我回傳 (-1, [])；否則從終點沿前驅走回起點，再翻轉得到路徑。每次成功鬆弛 最多產生一個新堆項目，所以惰性實作的時間是 O((V + E) log E)，空間是 O(V + E)。 固定寬度整數語言使用 64 位元距離。我會測試過期項目、平行邊、零權重邊、等長路徑、起終點相同、 不可達，以及負權重邊被拒絕的情況。」
常見錯誤
- 不確認負權重邊就執行 Dijkstra → 貪心確定性證明失效 → 把非負邊權重寫成明確前提，並拒絕不合法輸入。
- 第一次鬆弛到終點就結束 → 最早發現的路徑可能很昂貴 → 只在終點的目前項目出堆時結束。
- 不跳過堆中的過期項目 → 舊距離會重複掃描出邊 → 檢查
distance != distances[node]。 - 節點第一次入堆就標記已拜訪 → 後續更短路徑無法更新 → 只有目前最小項目出堆才算確定。
- 使用鄰接矩陣 → 稀疏圖也占用
O(V^2)記憶體 → 使用O(V + E)的鄰接串列。 - 等長距離也更新前驅，卻沒有平手規則 → 零權重環會讓路徑選擇反覆變化 → 任意最短路徑情境只處理嚴格改善。
- 題目要求路徑卻只保留距離 → 無法完成回傳合約 → 每次嚴格改善時記錄前驅，搜尋後還原。
- 不加說明就聲稱堆實作是
O(E log V)→ 惰性重複項目可能讓堆規模達到E→
寫出 O((V + E) log E)，再解釋常見 decrease-key 界線。
- 用 32 位元整數儲存距離 → 路徑長度可能遠超約 21 億 → 使用 Python 整數或 64 位元型別。
- 測試只檢查最終距離 → 錯誤的前驅鏈不會暴露 → 同時檢查路徑端點、邊和總權重。
追問與應對
追問 1：如果只需要最短距離呢？
移除 previous 陣列和路徑還原即可。搜尋流程、證明和漸進複雜度不變，只是少了一個 O(V) 的 節點陣列。終點目前項目出堆時依然可以提前結束。
追問 2：如果要查詢每個起點到所有節點的距離呢？
對每個節點執行一次本實作，代價為 O(V(V + E) log E)。稠密圖可考慮 Floyd-Warshall， 時間 O(V^3)、空間 O(V^2)，並能處理沒有負環時的負權重邊。稀疏圖若有負權重邊但沒有 負環，可考慮透過重新加權後重複執行 Dijkstra 的 Johnson 演算法。選擇要依據圖密度和查詢量。
追問 3：如果允許負權重邊呢？
一般有向圖使用 Bellman-Ford。它反覆鬆弛所有邊，時間為 O(VE)；額外一輪仍能成功鬆弛， 代表存在起點可達的負環。反例 0 -> 1 = 2、0 -> 2 = 5、2 -> 1 = -10 中， 提前結束的 Dijkstra 會把終點 1 確定為 2，但經過節點 2 的真實最短距離為 -5。
追問 4：如果圖是 DAG，但邊權重可能為負呢？
先做拓撲排序，再按拓撲順序把每條出邊鬆弛一次。所有前驅一定先於後繼處理，所以負權重邊也安全， 總時間為 O(V + E)。在更強的無環合約下，它比 Bellman-Ford 和 Dijkstra 都更合適。
追問 5：如果所有邊權重只有 0 或 1 呢？
使用雙端佇列做 0-1 BFS。零權重邊鬆弛後推到佇列前端，權重 1 的邊推到後端；佇列會維持距離 非遞減順序，不需要堆，時間降為 O(V + E)。
追問 6：如果邊會頻繁更新呢？
更新不頻繁時，修改對應邊後重新執行 Dijkstra 最容易驗證。若更新頻繁且延遲要求嚴格，才考慮 動態最短路徑或快取單源最短路徑樹並做失效處理；是否值得取決於更新與查詢比例、圖結構和規模。 不能假設一條邊變化只影響它的兩個端點。
追問 7：如何回傳字典順序最小的最短路徑？
只用嚴格距離比較無法完成，因為它會保留第一條等長路徑。先釐清字典順序合約。一種方案是先求 最短距離，再把候選轉移限制為滿足最短距離等式的邊，之後在確保仍能到達終點的前提下選擇最小 下一節點。零權重環需要額外防環處理。小規模輸入也可把完整路徑 tuple 放入堆中比較，但複製和 比較成本可能很高。