1514. Path with Maximum Probability

[zeikar]

Problem link

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

Problem Summary

간선에 확률이 있는 그래프가 주어진다. 시작점에서 끝점으로 갈 때 확률의 최대를 구하는 문제.

Solution

그냥 다익스트라를 돌려주면 된다.

일반 다익스트라가 합이 최소가 되게 한다면 여기서는 곱이 최대가 되게 뽑아주면 된다.

Source Code

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:
        graph = defaultdict(list)
        for i in range(len(edges)):
            graph[edges[i][0]].append((edges[i][1], succProb[i]))
            graph[edges[i][1]].append((edges[i][0], succProb[i]))
        
        prob = [0] * n
        prob[start_node] = 1
        pq = [(-1, start_node)]
        while len(pq) > 0:
            current = heapq.heappop(pq)
            (p, c) = current
            p *= -1
            if c == end_node:
                return p

            for g in graph[c]:
                next = g[0]
                np = p * g[1]

                if prob[next] < np:
                    heapq.heappush(pq, (-np, next))
                    prob[next] = np

        return 0.0