1514. Path with Maximum Probability

問題其實滿簡單的，就是單源最短路徑問題的延伸。每條邊有不同的權重且都介於[0,1]，既然權重沒有負數，那便可以直接用 Dijkstra’s algorithm 去解這問題，時間複雜度為O(|E|+|V|log|V|)。

class Compare{
public:
    bool operator()(const pair<int, double>& a, const pair<int, double>& b){
        return a.second > b.second;
    }
};
class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
        vector<unordered_map<int, double>> adj_with_prob(n, unordered_map<int, double>());
        // adjancy with probability
        for(size_t i=0; i<edges.size(); i++){
            adj_with_prob[edges[i][0]].insert({edges[i][1], succProb[i]});
            adj_with_prob[edges[i][1]].insert({edges[i][0], succProb[i]});
        }
        vector<double> maxProb = vector<double>(n, 0);
        vector<bool> traveled = vector<bool>(n, false);
        maxProb[start] = 1;
        int current = start;

        while(current != -1 && current != end){
            traveled[current] = true;
            for(auto neighbor: adj_with_prob[current]){
                int neighborNode = neighbor.first;
                if(! traveled[neighborNode]){
                    double prob = maxProb[current]*adj_with_prob[current][neighborNode];
                    maxProb[neighborNode] = prob > maxProb[neighborNode] ? prob : maxProb[neighborNode];
                }
            }
            double estimatedMaxProb = 0;
            current = -1;
            for(size_t i=0; i<n; i++){
                if(!traveled[i] && maxProb[i] > estimatedMaxProb){
                    estimatedMaxProb = maxProb[i];
                    current = i;
                }
            }
        }
        return maxProb[end];
    }
};

先把起點 start 的機率初始化為1，其他節點都預設為0。從起點開始走訪 current = start，每次走訪都檢視還沒走過的 current 鄰點 neighbor，如果 maxProb[neighbor] < maxProb[current] * p(current, neighbor)(current到neighbor的機率) 就更新 maxProb[neighbor]。當所有鄰點都檢視完後則更新current為走訪過的節點，再從maxProb 挑最大機率且還未走過的節點當作下一個current，直到沒有節點可走或找到maxProb[end]為止。