1514. Path with Maximum Probability | 1846

 1class Solution:
 2    def maxProbability(
 3        self,
 4        n: int,
 5        edges: List[List[int]],
 6        succProb: List[float],
 7        start_node: int,
 8        end_node: int,
 9    ) -> float:
10        # variation of dijkstras
11        # probability ranges from 1 to 0
12        # to still use min heap, we can use "fail rate"
13        # fail_rate[start_node] = 0
14        # shortest path -~> lowest fail rate
15
16        # dijkstra is okay with undirected and/or cycles
17
18        # build adj dict
19        adj = defaultdict(list)
20        for i in range(len(edges)):  # not necessarily n
21            adj[edges[i][0]].append([1 - succProb[i], edges[i][1]])
22            adj[edges[i][1]].append([1 - succProb[i], edges[i][0]])
23
24        # build dist i.e. fail rate
25        dist = [1] * n
26        dist[start_node] = 0
27
28        # build min heap pq
29        pq = [(0, start_node)]  # fail_rate, node
30
31        while pq:
32            fail_rate, node = heapq.heappop(pq)
33
34            if fail_rate > dist[node]:
35                continue
36
37            if node == end_node:  # early exit, guaranteed best result with pq
38                return 1 - fail_rate
39
40            for node_to_neighbor_fail_rate, neighbor in adj[node]:
41                # new fail rate = 1 - new pass rate = 1 - ((1-old_fail_rate)*(1-new_fail_rate))
42                new_fail_rate = 1 - ((1 - fail_rate) * (1 - node_to_neighbor_fail_rate))
43                if new_fail_rate < dist[neighbor]:
44                    dist[neighbor] = new_fail_rate
45                    heapq.heappush(pq, (new_fail_rate, neighbor))
46
47        return 0