Problem statement

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

Solution

Note, that if we take minus logarithms of our probabilities, what we actually need to find is shortest distance between start and end. Classical way to do it is to use Dijkstra algorithm.

Complexity

Time complexity O(E + V * log V) if we use heap as in the following code.

Code

class Solution:
    def maxProbability(self, n, edges, succProb, start, end):
        dist = [float('inf')] * n
        dist[start] = 0
        G = defaultdict(list)
        
        for i, (a, b) in enumerate(edges):
            G[a].append((b, -math.log(succProb[i])))
            G[b].append((a, -math.log(succProb[i])))
        
        heap = [(0, start)]

        while heap:
            min_dist, idx = heappop(heap)
            if idx == end: return math.exp(-min_dist)
            for neibh, weight in G[idx]:
                cand = min_dist + weight
                if cand < dist[neibh]:
                    dist[neibh] = cand
                    heappush(heap, (cand, neibh))
                    
        return 0