MediumArrayGraphHeap (Priority Queue)Shortest Path

Path with Maximum Probability

1 approach, code in every language

You are given an undirected weighted graph of `n` nodes labeled `0` to `n - 1`. Each edge is described by `edges[i] = [a, b]` together with a success probability `succProb[i]`, the chance of successfully traversing that edge.

Given a `start` node and an `end` node, return the maximum probability of successfully travelling from `start` to `end` along some path. The probability of a path is the product of the success probabilities of its edges.

If no path connects `start` and `end`, return `0`. Answers within `1e-5` of the true value are accepted.

Example 1

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

Output: 0.25000

Going 0 -> 1 -> 2 gives 0.5 * 0.5 = 0.25, which beats the direct edge 0 -> 2 at 0.2.

Example 2

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

Output: 0.00000

There is no edge that connects node 2 to the rest of the graph, so end is unreachable and the probability is 0.

Constraints

2 <= n <= 10^4
0 <= start, end < n
start != end
0 <= a, b < n
a != b
0 <= succProb.length == edges.length <= 2 * 10^4
0 <= succProb[i] <= 1
There is at most one edge between any two nodes.

Modified Dijkstra with a Max-Heap

Run Dijkstra with a max-heap ordered by probability, multiplying edge probabilities along the way; return the probability when end is popped.

Loading animation…

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

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

Time

O(E log V)

Space

O(V + E)

Because every factor lies in [0, 1], no path can improve a node after it is settled, mirroring Dijkstra's greedy correctness with a max-heap.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Most Reliable Parcel Route is our own problem on the technique behind Path with Maximum Probability: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free