#1514

Path with Maximum Probability

specialist · 625 · lc medium +29 · failed · 65.5% accepted · 3,879 likes · top 70%

Description

An undirected graph has n nodes (0-indexed) with edges edges[i] = [a, b] and corresponding traversal probabilities succProb[i]. Find the path from start to end that maximizes the product of edge probabilities and return that probability. Return 0 if no path exists. Answers within 1e-5 of the true value are accepted.

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: There are two paths from start to end, one having a probability of success = 0.2 and the other has 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 = 2

Output: 0.30000

Example 3:

Input: n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2

Output: 0.00000

Explanation: There is no path between 0 and 2.

Code

1

2

3

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float: