Last Updated: 26 Mar, 2021

Path With Maximum Probability

Moderate

Asked in companies

Solve now

Problem statement

You are given an undirected unweighted graph and an array 'sProability' which denotes the probability of traversing edges such that 'sProability[i]' denotes the probability of traversing ith edge. You are given the start and end vertex, You need to determine the maximum path probability on going from start to end vertex if there is no path from start to end return 0.

Input Format

The first line of input contains an integer 'T', the number 
of test cases.

The first line of the test case contains four integers ‘N’, 
‘M’, 'START', 'END' denoting the number of vertices, edges, starting vertex, and ending vertex.

The next ‘M’ lines describe the edge. Each edge is 
characterized by two integers ‘A’ and ‘B’ where ‘A’ and ‘B’ denotes the endpoints of the edge.

The last line of each test case contains ‘M’ space-separated floating-point number denoting the probability of traversing ith edge.

The edges[i][0], edges[i][1] contains the vertex that is 
connected to the edge.

Output Format

Return the maximum probability of path from start to end vertex up to 6 decimal places. If there is no path, return 0.

Note:

Graph does not contain self-loops.

Constraints

1 <= T <= 10
1 <= N <= 5 * 10 ^ 4
1 <= M <= min((N * (N - 1) / 2),10^5)
0 <= VERTEX VALUE, START, END <= N - 1
0 <= sProability[i] <= 1

Time Limit: 1 second

Solve now

Approaches

01 Approach

Traverse all the paths from start to end and then one with maximum probability is the answer.

Algorithm :

Create a boolean visited array. Start the depth-first search from the ‘start’ vertex such that it will give maximum probability from start to end.
If current vertex equal to end return 1.
Mark the current vertex true in the ‘visited’ array. Now iterate all the children of the current node such that it will give maximum probability from the current child’s vertex to end. Then multiply this with a probability of edge from the current node to children. If it is greater than the answer, replace the answer with the value.
After iterating all children mark the current node false in the visited array.
Return the answer.

Solve now

02 Approach

Use the Dijkstra algorithm from the start vertex and it will give maximum probability to all other vertices.

Algorithm:

Create a probability array and visited array and max priority queue ‘pq’ of pair of double and int. Start Dijkstra from start vertex.Push the pair of start vertex and 1 in the ‘pq’.
Pop the topmost node from the ‘pq’. Mark the current node as visited.If it is equal to ‘end’ vertex return the probability corresponding to the current vertex.
Iterate the children of the current node. If the child is marked as a true move to the current vertex.
Push the child vertex and probability of child by multiplying the probability of edge and current vertex probability.
After Dijkstra, if nothing is returned then return 0.

Solve now