Problem Statement in English

You’re given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where $edges[i] = [a_i, b_i]$ is an undirected edge connecting the nodes a and b with a success probability of $succProb[i]$.

Return the maximum probability path value of reaching from node start to node end.

If there is no path from start to end, return 0.

Approach

The idea is that we always want to explore the path with the maximum probability first.

This can be achieved using a max-heap (priority queue) where we store the negative of the probabilities (since Python’s heapq is a min-heap by default).

If we reach the end node, we return the accumulated probability. If we exhaust all possibilities without reaching end, we return 0.

Solution in Python


from heapq import heappush, heappop

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

        for i, p in enumerate(edges):
            u, v = p
            prob = succProb[i]

            adj[u].append((prob, v))
            adj[v].append((prob, u))

        maxheap = [(-1, start_node)]
        seen = set()

        while maxheap:
            prob, node = heappop(maxheap)

            if node in seen:
                continue
            seen.add(node)

            if node == end_node:
                return -prob

            for p, n in adj[node]:
                if n in seen:
                    continue

                heappush(maxheap, (prob * p, n))

        return 0

Complexity

  • Time: $O((V + E) \log V)$
    Where V is the number of vertices and E is the number of edges in the graph.

  • Space: $O(V + E)$
    Where V is the number of vertices in the graph, and E is the number of edges.

And we are done.