We have an undirected weighted graph with n nodes are (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of traversing that edge succProb[i].
Given two nodes start and end, find the path with the maximum probability of success to go from start to end and return its success probability.
If there is no path from start toend return 0.
Example :
Input: n=4, edges: [[0,1],[0,2],[1,3],[2,3]], success: [0.1,0.2,0.1,0,2], start: 0, end: 0
Output: 0.04
Solution:
We will use the Breadth-First Search to solve the problem. We will maintain a vector nodeProb of size n where nodeProb[i],
represents the maximum probability for reaching node i. We use a queue to implement BFS
Now to account for all possible paths from start to end with maximum probability we put only those nodes in the queue whose new probability for reaching them will be greater than the earlier probability, this way we will not end in an infinite loop by adding nodes again and again.
Code:
double maximumProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
int x,nxt;
double p;
vector<double> nodeProb(n,0);
vector<vector<pair<int,double>>> neighbours(n);
for(int i=0;i<edges.size();i++)
{
neighbours[edges[i][0]].push_back({edges[i][1],succProb[i]});
neighbours[edges[i][1]].push_back({edges[i][0],succProb[i]});
}
queue<int> q;
q.push(start);
nodeProb[start]=1;
while(!q.empty())
{
x=q.front();
q.pop();
for(auto neighbour:neighbours[x])
{
nxt=neighbour.first;
p=neighbour.second;
if(nodeProb[nxt]<nodeProb[x]*p)
{
nodeProb[nxt]=nodeProb[x]*p;
q.push(nxt);
}
}
}
return nodeProb[end];
}
Do share the post if you find it helpful and comment if you have some new insights about the problem.
Happy Programming
Programming ninja
If you have any doubts or any new insights, please share ConversionConversion EmoticonEmoticon