23.06.28 Today’s Leetcode

1514. Path with Maximum Probability (medium)

Failed with DFS Approaching

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        tree = defaultdict(dict)
        for i in range(len(edges)):
            a, b = edges[i]
            tree[a][b] = succProb[i]
            tree[b][a] = succProb[i]

        visited = [-1] * (1 + len(edges))

        # print(tree)
        @functools.lru_cache(None)
        def dfs(cur, prev, poss):
            if cur == end:
                return poss
            temp = 0
            for next_ in tree[cur].keys():
                if next_ == prev:
                    continue
                temp = max(temp, dfs(next_, cur, poss * tree[cur][next_]))
            return temp

        return dfs(start, -1, 1)

BFS Approach

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start: int, end: int) -> float:
        # Adjacency list
        adj = [[] for _ in range(n)]
        for i in range(len(edges)):
            u, v = edges[i]
            p = succProb[i]
            adj[u].append((v, p))
            adj[v].append((u, p))

        # Distances array
        dist = [0.0] * n
        dist[start] = 1.0

        # Queue for BFS
        queue = deque([start])

        while queue:
            curr = queue.popleft()

            for node, prob in adj[curr]:
                new_prob = dist[curr] * prob

                if new_prob > dist[node]:
                    dist[node] = new_prob
                    queue.append(node)

        return dist[end]