HardRating 2364
2203. Minimum Weighted Subgraph With the Required Paths
graphheap-priority-queueshortest-path
解題說明
Minimum Weighted Subgraph With the Required Paths
題目描述： 給定一個有向加權圖，有 n 個節點和 m 條邊。給定三個節點 src1、src2、dest。找到一個最小權重的子圖，使得 src1 和 src2 都能到達 dest。回傳最小總邊權，若不可能則回傳 -1。
解題思路： 關鍵觀察：最優解中，從 src1 到 dest 的路徑和從 src2 到 dest 的路徑會在某個中間節點 m 合流，之後共用從 m 到 dest 的路徑。
因此，答案 = min over all nodes m of: dist1[m] + dist2[m] + distR[m]，其中：
- dist1[m] = src1 到 m 的最短距離（正向圖）
- dist2[m] = src2 到 m 的最短距離（正向圖）
- distR[m] = m 到 dest 的最短距離 = dest 到 m 在反向圖上的最短距離
步驟：
- 在正向圖上從 src1 跑 Dijkstra，得到 dist1[]。
- 在正向圖上從 src2 跑 Dijkstra，得到 dist2[]。
- 在反向圖上從 dest 跑 Dijkstra，得到 distR[]。
- 答案 = min(dist1[m] + dist2[m] + distR[m]) for all m。
C++ 解法
複雜度分析
時間複雜度：O((n + m) log n) — 三次 Dijkstra，每次 O((n + m) log n)。
空間複雜度：O(n + m) — 正向圖、反向圖各 O(m)，距離陣列 O(n)。
虛擬碼
1. Build forward adjacency list and reverse adjacency list. 2. Run Dijkstra from src1 on forward graph → dist1[]. 3. Run Dijkstra from src2 on forward graph → dist2[]. 4. Run Dijkstra from dest on reverse graph → distR[]. 5. For each node m: if all three distances are finite, candidate = dist1[m] + dist2[m] + distR[m]. 6. Return minimum candidate, or -1 if none.
其他解法
-
Steiner 樹精確演算法：此問題本質是求 {src1, src2, dest} 三個終端的最小 Steiner 樹。可用 DP on subsets：dp[S][v] 表示連接終端子集 S 且以 v 為根的最小代價。時間複雜度 O(3^k * n + 2^k * m log n)，k=3 時為 O(n + m log n)。但對此題三源合流的觀察更簡潔。
-
列舉合流邊：不枚舉合流節點，而是枚舉合流邊 (u, v, w)。分別考慮 src1 和 src2 在邊的哪一端合流。但這比枚舉節點更複雜且無效率優勢。
延伸思考
- 若有 K 個源點（而非 2 個）都需要到達 dest，如何擴展此方法？K 較大時有什麼更好的方法？
- 若邊權可以為負（但無負環），Dijkstra 不可用，應改用什麼演算法？
- 若圖是無向圖，合流節點的概念是否仍然成立？解法需要怎麼修改？