Path with Maximum Probability
You are given an undirected weighted graph of n nodes, numbered from 0 to n - 1, represented by an edge list where edges[i] = [a, b] is an undirected edge connecting nodes a and b with a probability of success succProb[i] when traversing that edge.
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 to end, return 0. Your answer will be accepted if it differs from the correct answer by at most 1e-5.
Example 1
Input
n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2Output
0.25There are two paths from start to end: one has probability 0.2, and the other has probability 0.5 * 0.5 = 0.25.
Example 2
Input
n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2Output
0.3The direct path from 0 to 2 has probability 0.3, which is greater than the path through node 1 with probability 0.25.
Constraints
- 2 <= n <= 10^4
- 0 <= start, end < n
- start != end
- 0 <= a, b < n
- a != b
- 0 <= succProb.length == edges.length <= 2*10^4
- 0 <= succProb[i] <= 1
- There is at most one edge between every two nodes.
Asked at 5 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.