Path with Maximum Probability

Leetcode Problem:

• Path with Maximum Probability

Summary

• Find the path with the maximum probability of success to go from start to end in an undirected weighted graph.

Approach

• This solution uses a breadth-first search (BFS) approach with a priority queue
• It starts from the start node and explores all its neighbors
• For each neighbor, it calculates the maximum probability of success and updates the visited array
• The process continues until the end node is reached or all nodes are visited.

Complexity

• O(n + m * log n) where n is the number of nodes and m is the number of edges

Explain

• The code defines a graph using an adjacency list representation
• It initializes a visited array to keep track of visited nodes and a queue to store nodes to be visited
• The main function takes the number of nodes, edges, and probabilities as input and returns the maximum probability of success
• It uses a BFS approach to explore all nodes and calculates the maximum probability of success for each node
• The time complexity is O(n + m * log n) due to the priority queue operations.

Solution Code:

struct Node{
    int nod;
    double prob;
};
struct QNode{
    int nod;
    double probSum;
};
class Solution {
public:
    vector v[10001];
    double visited[10001] = {0};
    queue q;
    double maxProbability(int n, vector>& edges, vector& succProb, int start_node, int end_node) {
        double ans = 0;
        for(int i = 0 ; i < edges.size();i++){
            double prob = succProb[i];
            int a = edges[i][0];
            int b = edges[i][1];
            v[a].push_back({b, prob});
            v[b].push_back({a, prob});
        }
        visited[start_node] = 1;
        q.push({start_node, 1});
        while(!q.empty()){
            QNode nod = q.front();
            q.pop();
            if (nod.nod == end_node){
                if(ans < nod.probSum){
                    ans = nod.probSum;
                }
            }
            for(int i = 0 ; i < v[nod.nod].size(); i++){
                Node nextNod = v[nod.nod][i];
                if(nextNod.nod != end_node && visited[nextNod.nod] >= nod.probSum * nextNod.prob){
                    continue;
                }
                if (visited[nextNod.nod] < nod.probSum * nextNod.prob){
                    visited[nextNod.nod] = nod.probSum * nextNod.prob;
                }
                q.push({nextNod.nod, nod.probSum * nextNod.prob});
            }
        }
        
        return ans;

    }
};