MediumRating 1846
1514. Path with Maximum Probability
arraygraphheap-priority-queueshortest-path
解題說明
Path with Maximum Probability
題目描述：
給定一個無向加權圖，邊的權重代表成功通過的機率（0 到 1 之間）。求從起點 start 到終點 end 的最大成功機率。若無法到達回傳 0。
解題思路： 這是 Dijkstra 最短路徑的變體。傳統 Dijkstra 求最小距離（加法），這裡求最大機率（乘法）。由於機率相乘的單調性（0~1 之間的數越乘越小），使用最大堆（max-heap）代替最小堆，每次取出機率最大的節點進行鬆弛。
初始化起點機率為 1（出發點的成功機率），其餘為 0。每次從堆中取出機率最大的節點 u，對其鄰居 v 嘗試更新 prob[v] = max(prob[v], prob[u] * edgeProb(u,v))。當取出的是終點時即可回傳。
C++ 解法
複雜度分析
時間複雜度：O((n + E) log n) — Dijkstra 搭配堆，E 為邊數。
空間複雜度：O(n + E) — 鄰接表 O(E)，機率陣列和堆 O(n)。
虛擬碼
1. Build adjacency list from edges and succProb
2. Initialize prob array: prob[start] = 1.0, all others = 0.0
3. Push (1.0, start) into max-heap
4. While heap is not empty:
a. Pop (curProb, u)
b. If u == end, return curProb
c. If curProb < prob[u], skip (stale entry)
d. For each neighbor (v, edgeProb) of u:
- newProb = curProb * edgeProb
- If newProb > prob[v]:
prob[v] = newProb
Push (newProb, v) into heap
5. Return 0.0 (unreachable)其他解法
Bellman-Ford 變體 O(n * E)：迭代 n-1 次，每次遍歷所有邊嘗試鬆弛。不需要堆，但時間複雜度較高。
BFS / SPFA：使用佇列的 SPFA（Shortest Path Faster Algorithm）變體，每次更新時將節點加入佇列。平均情況快但最壞情況 O(nE)。
對數轉換 + 標準 Dijkstra：取 -log(prob) 將乘法轉為加法，最大機率轉為最短距離。可直接用標準最小堆 Dijkstra。數學上等價但有浮點精度風險。
延伸思考
- 若邊的機率會動態更新，如何高效重新計算最大機率路徑？
- 若要求「至少 k 條不同路徑中的最大機率」，如何修改？
- 此問題的最大機率乘積與最短路的最小距離加法，在數學上有什麼對應關係？