631. Path with Maximum Probability
You are given an undirected graph of n nodes labeled 0 to n − 1, described by an edge list edges where edges[i] = [a, b], and a parallel array succProb where succProb[i] is the probability of crossing that edge successfully.
Crossings are independent, so the success probability of a whole path is the product of its edge probabilities. Given two nodes start and end, return the highest success probability among all paths from start to end. If no path connects them, return 0.
Because the answer is a probability, report it rounded to exactly 5 decimal places — the judge compares that fixed-format text.
Example 1:
Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5, 0.5, 0.2], start = 0, end = 2
Output: 0.25000
Explanation: Two routes lead from 0 to 2: the direct edge with probability 0.2, and the detour 0 → 1 → 2 with probability 0.5 × 0.5 = 0.25. The detour is more reliable, so the answer is 0.25.
Example 2:
Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5, 0.5, 0.3], start = 0, end = 2
Output: 0.30000
Explanation: Same graph, but now the direct edge succeeds 30% of the time — better than the detour's 25%, so the direct hop wins.
Constraints:
- 2 ≤ n ≤ 10⁴
- 0 ≤ e = edges.length ≤ 2 · 10⁴
- 0 ≤ a, b < n, a ≠ b, and there is at most one edge between any pair of nodes
- 0 ≤ succProb[i] ≤ 1 (given with at most 5 decimal digits)
- 0 ≤ start, end < n, start ≠ end
Hints:
This is shortest-path in disguise: instead of minimizing a sum of weights you are maximizing a product of probabilities. Every probability is <= 1, so extending a path can never make it MORE likely — that plays the same role as non-negative edge weights.
Run Dijkstra with the comparisons flipped: a max-heap keyed on the probability of reaching each node, popping the most-probable unsettled node and relaxing with multiplication (`best[v] < best[u] * p`).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5, 0.5, 0.2], start = 0, end = 2
Expected output: 0.25000