1514.Path-with-Maximum-Probability.md

1514. Path with Maximum Probability

Difficulty: Medium

URL

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

Solution

Approach 1:

The code is shown below:

import heapq

class State:
    def __init__(self, id, max_prob_from_start):
        self.id = id
        self.prob_from_start = max_prob_from_start
    
    def __lt__(self, other):
        return self.prob_from_start > other.prob_from_start

class Solution:
    def dijkstra(self, graph, n, start, end):
        max_prob = [-1] * n
        max_prob[start] = 1
        pq = [State(start, 1)]
        
        while len(pq) != 0:
            cur = heapq.heappop(pq)
            cur_id, prob_from_start = cur.id, cur.prob_from_start
            if cur_id == end:
                return prob_from_start
            if prob_from_start < max_prob[cur_id]:
                continue
            for edge in graph[cur_id]:
                next_id, prob = edge
                next_prob = prob_from_start * prob
                if next_prob > max_prob[next_id]:
                    max_prob[next_id] = next_prob
                    heapq.heappush(pq, State(next_id, next_prob))
                        
        # no path exists
        return 0
    
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        graph = [[] for _ in range(n)]
        for i in range(len(edges)):
            edge = edges[i]
            graph[edge[0]].append((edge[1], succProb[i]))
            graph[edge[1]].append((edge[0], succProb[i]))
            
        return self.dijkstra(graph, n, start, end)