題目描述:有 n 個節點(編號 1 到 n)的有向加權圖,以及一組有向邊 times[i] = [ui, vi, wi] 表示從節點 ui 到 vi 的傳輸時間為 wi。從節點 k 發出信號,求信號傳遞到所有節點所需的最短時間。若無法到達所有節點,回傳 -1。
解題思路:此題本質是「單源最短路徑(Single-Source Shortest Path)」問題,求從節點 k 出發到所有其他節點的最短路徑,最後取最大值(瓶頸即為傳遞給所有節點的最慢時間)。
使用 Dijkstra's Algorithm(戴克斯特拉演算法):
(distance, node) 對,起點 k 的距離為 0;所有節點初始距離設為無限大。u(此距離即為最短距離,因為邊權重非負)。若已處理過 u 則跳過。對 u 的所有鄰居 v 嘗試鬆弛:若 dist[u] + weight < dist[v],更新 dist[v] 並推入堆。Dijkstra 適用條件:邊權重必須為非負值(本題 wi >= 1 滿足此條件)。若有負權重邊,需改用 Bellman-Ford 演算法。
時間複雜度:O((V + E) log V) — 其中 V = n(節點數),E = times.size()(邊數)。每個節點最多被加入堆一次後確認最短距離(V 次 pop),每條邊最多觸發一次 push 操作(E 次 push),每次堆操作為 O(log V)(堆大小上限為 V+E,但通常以 V 估計)。
空間複雜度:O(V + E) — 鄰接表儲存所有邊需 O(E),dist 陣列需 O(V),最小堆最壞情況下需 O(E)(每條邊可能對應一個堆元素)。
1. Build adjacency list adj[] from times: adj[u].append((v, w))
2. Initialize dist[1..n] = INF, dist[k] = 0
3. Push (0, k) to min-heap pq
4. While pq not empty:
a. Pop (d, u) with minimum distance
b. If d > dist[u]: skip (outdated entry)
c. For each neighbor (v, w) of u:
- If dist[u] + w < dist[v]:
- dist[v] = dist[u] + w
- Push (dist[v], v) to pq
5. maxDist = max(dist[1..n])
6. If any dist[i] == INF: return -1
7. Return maxDistBellman-Ford O(V·E):對所有邊進行 V-1 輪鬆弛操作,每輪遍歷所有邊。可處理負權重邊,且可偵測負權重環(第 V 輪仍能鬆弛則表示存在負環)。本題保證權重為正(wi >= 1),因此 Dijkstra 已是最佳選擇,Bellman-Ford 的 O(V·E) 較慢。
Floyd-Warshall O(V³):計算所有點對之間的最短路徑。對本題而言只需從單一源點出發,Floyd-Warshall 會計算多餘的資訊,時間複雜度更高,不建議使用。但若同一張圖需要回答多次「從不同源點出發」的查詢,Floyd-Warshall 預處理後每次查詢為 O(1),總效益較佳。