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 不適用，該用什麼演算法？
若要找次短路徑的數量，如何修改演算法？

Number of Ways to Arrive at Destination — CaffeCode