Description
Given a graph with edge probabilities, find the path from start to end with maximum probability. Return 0 if no path exists.
Examples
Input:
n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2Output:
0.25Explanation:
Path 0 -> 1 -> 2 has probability 0.5 * 0.5 = 0.25.
Input:
n = 3, edges = [[1]], succProb = [0.5,0.5,0.2], start = 0, end = 2Output:
0.25Explanation:
Minimal case with a single edge.
Input:
n = 4, edges = [[0,1],[0,2],[1,3],[2,3]], succProb = [0.8,0.3,0.6,0.9], start = 0, end = 3Output:
0.48Explanation:
Two possible paths: 0 -> 1 -> 3 has probability 0.8 * 0.6 = 0.48, and 0 -> 2 -> 3 has probability 0.3 * 0.9 = 0.27. The maximum probability path is 0 -> 1 -> 3 with 0.48.
Constraints
- •
2 ≤ n ≤ 10⁴