Medium
Related Topics: Array / Graph / Heap (Priority Queue) / Shortest Path
LeetCode Source

解題想法

首先，建立一個數組 dist，用來儲存從起始節點到每個節點的最大概率。把 dist[start] 設為 1，因為一開始我們就在起始節點，概率就是 1。

然後，進行最多 n-1 次迭代（其中 n 是節點的總數）。在每次迭代中，檢查每條邊，並更新鄰近節點的到達概率。

對於每條邊 (u, v)，如果從 u 到 v 的概率（即 dist[u] * succProb[i]）比當前已知的到達 v 的概率（dist[v]）還高，就更新 dist[v]。如果從 v 到 u 的概率更高，也更新 dist[u]。

最後，當所有迭代完成後，dist[end] 就會顯示從起始節點到終點節點的最大概率。如果沒有路徑，這個值會是 0。

Complexity

Time Complexity: O(n * E)
Space Complexity: O(n)

Python

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        dist = [0] * n
        dist[start] = 1
        
        for _ in range(n - 1):
            updated = False
            for i, (u, v) in enumerate(edges):
                if dist[u] * succProb[i] > dist[v]:
                    dist[v] = dist[u] * succProb[i]
                    updated = True
                if dist[v] * succProb[i] > dist[u]:
                    dist[u] = dist[v] * succProb[i]
                    updated = True
            if not updated:
                break
        
        return dist[end]

C++

class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start_node, int end_node) {
        vector<double> maxProb(n, 0.0);
        maxProb[start_node] = 1.0;

        for (int i = 0; i < n - 1; ++i) {
            bool updated = false;
            for (int j = 0; j < edges.size(); ++j) {
                int u = edges[j][0];
                int v = edges[j][1];
                double prob = succProb[j];

                if (maxProb[u] * prob > maxProb[v]) {
                    maxProb[v] = maxProb[u] * prob;
                    updated = true;
                }
                if (maxProb[v] * prob > maxProb[u]) {
                    maxProb[u] = maxProb[v] * prob;
                    updated = true;
                }
            }
            if (!updated) break;
        }

        return maxProb[end_node];
    }
};