Leetcode 1325 Solution
This article provides solution to leetcode question 1325 (path-with-maximum-probability)
Access this page by simply typing in "lcs 1325" in your browser address bar if you have bunnylol configured.
Leetcode Question Link
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