Leetcode 1325 Solution

This article provides solution to leetcode question 1325 (path-with-maximum-probability)
Categories:
Tags:
Access this page by simply typing in "lcs 1325" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/path-with-maximum-probability

Solution

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        graph = collections.defaultdict(list)
        for (src, dst), prob in zip(edges, succProb):
            graph[src].append((dst, prob))
            graph[dst].append((src, prob))

        q = []
        heapq.heappush(q, (-1, start))
        visited = set()

        while q:
            node_prob, node = heapq.heappop(q)

            if node in visited:
                continue

            if node == end:
                return -node_prob

            visited.add(node)

            for nei_node, prob in graph[node]:
                if nei_node in visited:
                    continue

                heapq.heappush(q, (node_prob * prob, nei_node))

        return 0