Path with Maximum Probability

Intuition

The probability of a path is the product of its edge probabilities, and since every factor lies in [0, 1], extending a path can only keep the value the same or shrink it. Maximizing a product of non-negative factors behaves like a shortest-path search once we treat "more probable" as "closer", so a greedy Dijkstra-style expansion with a max-heap works. We always finalize the most probable node first, which guarantees its recorded probability is optimal and never needs revising. The only change from standard Dijkstra is multiplying probabilities instead of adding weights. If end is never popped, no path exists and the answer is 0.

Algorithm walkthrough

1. 1Build an undirected adjacency list; each edge contributes (neighbor, probability) to both of its endpoints.
2. 2Track the best probability to reach each node, set prob[start] = 1, and push (1.0, start) onto a max-heap.
3. 3Pop the most probable node; if it is end, return its probability since no later path can improve on it.
4. 4Ignore stale pops whose probability is below the recorded best for that node.
5. 5For each neighbor, multiply the current probability by the edge probability; if that exceeds the neighbor's best, update it and push the neighbor.
6. 6If end is never reached before the heap empties, return 0.

Implementation

import heapq
from typing import List


class Solution:
    def maxProbability(
        self,
        n: int,
        edges: List[List[int]],
        succProb: List[float],
        start: int,
        end: int,
    ) -> float:
        graph = [[] for _ in range(n)]
        for i, (u, v) in enumerate(edges):
            graph[u].append((v, succProb[i]))
            graph[v].append((u, succProb[i]))

        prob = [0.0] * n
        prob[start] = 1.0
        heap = [(-1.0, start)]  # negate to emulate a max-heap

        while heap:
            p, node = heapq.heappop(heap)
            p = -p
            if node == end:
                return p
            if p < prob[node]:
                continue
            for nei, ep in graph[node]:
                np = p * ep
                if np > prob[nei]:
                    prob[nei] = np
                    heapq.heappush(heap, (-np, nei))

        return 0.0