Path with Maximum Probability (Leetcode 1514)

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

from collections import defaultdict
import heapq
class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        
        adj=defaultdict(list)
        for i in range(len(edges)):
            adj[edges[i][0]].append((edges[i][1],succProb[i]))
            adj[edges[i][1]].append((edges[i][0],succProb[i]))
            
        probarr=[0.0 for i in range(n)]
        probarr[start]=1.0
        pq=[]
        heapq.heapify(pq)
        # (node, succProb)
        heapq.heappush(pq,(start,-1.0))
        
        while(len(pq)>0):
            
            node,prob=heapq.heappop(pq)
            
            for i in adj[node]:
                adjnode=i[0]
                succProb=i[1]
                if(-prob*succProb>probarr[adjnode]):
                    probarr[adjnode]=-prob*succProb
                    heapq.heappush(pq,(adjnode,-probarr[adjnode]))
        
        return probarr[end]

Last updated