Path with Maximum Probability (LeetCode 1514)

The problem

You get an undirected graph with n nodes. Edge i joins edges[i] = [a, b] and succeeds with probability succProb[i]. The probability of a path is the product of its edge probabilities. Return the highest success probability of any path from start to end, or 0 if there is no path.

Input:  n = 3, edges = [[0,1], [1,2], [0,2]], succProb = [0.5, 0.5, 0.2], start = 0, end = 2
Output: 0.25

The direct edge 0–2 has probability 0.2. Going 0 → 1 → 2 gives 0.5 × 0.5 = 0.25, which is better.

How to think about it

Start with brute force. Enumerate every simple path from start to end with DFS and keep the best product. The number of paths can be exponential.

Compare with shortest path. Ordinary Dijkstra minimises a sum of non-negative weights. It works because extending a path can never make it better, so the first time a node is popped its distance is final.

The key insight: products of numbers ≤ 1 behave the same way, upside down. Every probability is between 0 and 1, so multiplying by another edge can only lower or keep the value. That is the same monotonic property, flipped. So run Dijkstra that maximises instead of minimising: always expand the node with the highest probability so far, and relax with p * w > best[v]. Python’s heapq is a min-heap, so push negated probabilities to get a max-heap. (Equivalently, take -log(p) as an edge weight and run normal Dijkstra; products become sums.)

Which pattern is this? Dijkstra on a modified cost. The tell is “best path” on a weighted graph where the cost combines monotonically along the path.

Approach

1. Build an adjacency list, adding each edge in both directions with its probability.
2. Set best[start] = 1.0 and every other node to 0. Push (-1.0, start).
3. Pop the node u with the highest probability p. If u is end, return p.
4. If p is below best[u], the entry is stale; skip it.
5. For each neighbour v with edge probability w, if p * w > best[v], update best[v] and push it.
6. If the heap empties, end is unreachable: return 0.

Solution

import heapq
from collections import defaultdict
def max_probability(n, edges, succProb, start, end):
    adj = defaultdict(list)
    for (a, b), p in zip(edges, succProb):
        adj[a].append((b, p)); adj[b].append((a, p))      # undirected
    best = [0.0] * n; best[start] = 1.0
    h = [(-1.0, start)]                                   # negate for a max-heap
    while h:
        p, u = heapq.heappop(h); p = -p
        if u == end: return p                             # first pop of end is optimal
        if p < best[u]: continue                          # stale entry
        for v, w in adj[u]:
            if p * w > best[v]:
                best[v] = p * w; heapq.heappush(h, (-best[v], v))
    return 0.0
# max_probability(3, [[0,1],[1,2],[0,2]], [0.5,0.5,0.2], 0, 2) -> 0.25

Dry run

The answer is 0.25. The older 0.2 entry for node 2 is still in the heap, but the better 0.25 entry pops first.

Complexity

• Time: O((V + E) log V). Each successful relaxation pushes one entry and each pop costs a log. Strictly, the lazy heap can hold up to E entries, which is the same bound up to a constant.
• Space: O(V + E). The adjacency list, best and the heap.

Edge cases and pitfalls

• No path returns 0.0 once the heap is empty.
• start == end returns 1.0 immediately.
• Using a min-heap without negating expands the least likely node first and breaks the algorithm.
• This only works because every probability is ≤ 1. With factors above 1, a longer path could beat a popped node and Dijkstra’s guarantee fails.
• Treating edges as directed misses paths; add both directions.

Related problems

• Network Delay Time (LeetCode 743): standard Dijkstra minimising a sum.
• Path With Minimum Effort (LeetCode 1631): Dijkstra where the path cost is a max.
• Cheapest Flights Within K Stops (LeetCode 787): when an extra constraint breaks plain Dijkstra.