743. Network Delay Time
解題說明
Network Delay Time
題目描述：有 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]並推入堆。 - 結果統計：處理完所有可達節點後，若仍有節點距離為無限大，表示不可達，回傳 -1；否則回傳所有最短距離中的最大值。
Dijkstra 適用條件：邊權重必須為非負值（本題 wi >= 1 滿足此條件）。若有負權重邊，需改用 Bellman-Ford 演算法。
C++ 解法
複雜度分析
時間複雜度：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 maxDist其他解法
Bellman-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)，總效益較佳。
延伸思考
- 若圖中存在負權重邊（但無負權重環），Dijkstra 演算法會給出錯誤答案，請舉一個具體反例說明為何會失敗，以及 Bellman-Ford 如何正確處理此情況。
- 本題要求找到「最慢傳遞時間」（所有最短路徑的最大值）。若改為「找到最多能傳遞到幾個節點，使得傳遞時間不超過 T」，如何在現有 Dijkstra 基礎上修改？
- 若邊的傳輸時間可能動態更新（例如網路故障導致某條邊的延遲增加），如何設計一個支援「更新邊權重並重新查詢最短路徑」的高效資料結構？