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