DSA problem
Path with Maximum Probability
You are given an undirected weighted graph of n nodes (0-indexed) represented by an edge list edges[i] = [a, b] where each edge has a success probability succProb[i] of traversal. Given two nodes start and end, return the maximum probability of success to traverse from start to end. If there is no path, return 0.
The probability of a multi-edge path is the product of the probabilities of its edges, since each edge succeeds independently. We want the path that maximizes this product. Naively trying all paths is exponential, so we need a graph-search strategy.
This problem is structurally identical to a shortest-path problem after a clever transformation. Since log(a * b) = log(a) + log(b), taking the negative logarithm of each probability turns the product-maximization into a sum-minimization with non-negative edge weights — exactly Dijkstra's setting. However, working in linear probability space is simpler and avoids floating-point issues from logarithms.
The optimal approach runs a Dijkstra variant using a max-heap keyed by current probability. Start by pushing (1.0, start), then repeatedly pop the highest-probability unsettled node and relax its neighbors by multiplying. The first time end is popped from the heap, that pop's probability is the answer. If the heap empties without reaching end, return 0. The structure runs in O((n + E) log n) time and O(n + E) space.
Examples
n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 20.25000n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 20.30000n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 20.00000Constraints
- 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 every two nodes.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.