MediumRating 2095
1976. Number of Ways to Arrive at Destination
dynamic-programminggraphtopological-sortshortest-path
解題說明
Number of Ways to Arrive at Destination
題目描述:給定一個加權無向圖,n 個節點(0 到 n-1)和若干邊。求從節點 0 到節點 n-1 的最短路徑數量,取模 10^9 + 7。
解題思路:使用 Dijkstra 演算法求最短距離的同時計算路徑數。維護 dist[v] 為到 v 的最短距離和 ways[v] 為到 v 的最短路徑數。當發現更短路徑時重置 ways,當發現等長路徑時累加 ways。初始 dist[0] = 0, ways[0] = 1。
C++ 解法
複雜度分析
時間複雜度:O(E log V) — 標準 Dijkstra 演算法的時間複雜度。
空間複雜度:O(V + E) — 鄰接表、距離和路徑數陣列。
虛擬碼
1. Build adjacency list
2. Init dist[0] = 0, ways[0] = 1, all others dist = INF, ways = 0
3. Push (0, node 0) to min-heap
4. While heap not empty:
a. Pop (d, u). If d > dist[u], skip
b. For each neighbor (v, w) of u:
- If dist[u] + w < dist[v]: update dist[v], ways[v] = ways[u], push to heap
- If dist[u] + w == dist[v]: ways[v] += ways[u] (mod)
5. Return ways[n-1]其他解法
Bellman-Ford + 路徑計數:用 Bellman-Ford 替代 Dijkstra(適用於有負權邊的情況)。鬆弛時同樣維護 ways 陣列。時間 O(VE),本題邊權非負故 Dijkstra 更優。
BFS(等權圖):若所有邊權相同,可用 BFS 計算最短路徑數。時間 O(V + E),但本題邊權不同,不適用。
延伸思考
- 若要找出所有最短路徑的實際路徑(不只是數量),如何記錄?
- 若圖中有負權邊,Dijkstra 不適用,該用什麼演算法?
- 若要找次短路徑的數量,如何修改演算法?