HardRating 1811

2642. Design Graph With Shortest Path Calculator

graphdesignheap-priority-queueshortest-path

在 LeetCode 上作答 ↗

解題說明

Design Graph With Shortest Path Calculator

題目描述：設計一個有向加權圖的資料結構，支援兩個操作：addEdge(edge) 新增一條有向邊；shortestPath(node1, node2) 計算 node1 到 node2 的最短路徑長度，若不可達返回 -1。

解題思路：使用鄰接表儲存圖，每次 shortestPath 查詢時執行 Dijkstra 演算法。由於邊的權重為正整數，Dijkstra 可以正確求解。

新增邊是 O(1)，最短路徑查詢是 O((V + E) log V)。

C++ 解法

複雜度分析

時間複雜度：addEdge O(1)；shortestPath O((V + E) log V) — Dijkstra 使用最小堆

空間複雜度：O(V + E) — 鄰接表和 Dijkstra 的距離陣列

虛擬碼

1. Initialize adjacency list from given edges
2. addEdge(edge):
   a. Append (to, weight) to adj[from]
3. shortestPath(node1, node2):
   a. Initialize dist array with INF, dist[node1] = 0
   b. Push (0, node1) to min-heap
   c. While heap not empty:
      - Pop (d, u) with minimum distance
      - If d > dist[u], skip (stale entry)
      - If u == node2, return d
      - Relax all edges from u
   d. Return -1 (unreachable)

其他解法

Floyd-Warshall 法：預計算所有節點對的最短路徑。初始化後 addEdge 需要 O(V^2) 更新。適合查詢多但新增邊少的場景。shortestPath O(1)，但 addEdge O(V^2)。
Bellman-Ford 法：如果圖中可能有負權邊，需要改用 Bellman-Ford。時間 O(VE)，比 Dijkstra 慢但更通用。本題權重為正所以 Dijkstra 最佳。

延伸思考

如果要支援刪除邊的操作，Dijkstra 方法如何調整？（提示：需要重新計算或使用更複雜的資料結構）
如果邊的權重可能為負數（但無負環），應該使用什麼演算法？
如果頻繁查詢相同的源點和目標，如何用快取優化？

Design Graph With Shortest Path Calculator — CaffeCode