1514. Path with Maximum Probability.md

1514. Path with Maximum Probability

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

solution

import collections

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:
        graph = collections.defaultdict(list)
        queue = collections.deque([start_node])

        for i, (a, b) in enumerate(edges):
            graph[a].append([b, i])
            graph[b].append([a, i])
        
        p = [0] * n
        p[start_node] = 1.0

        while queue:
            cur = queue.popleft()
            for nei, i in graph[cur]:
                if p[cur] * succProb[i] > p[nei]:
                    p[nei] = p[cur] * succProb[i]
                    queue.append(nei)
        return p[end_node]

时间复杂度：O()
空间复杂度：O()