Path with Maximum Probability
Last Updated: April 5, 2026
Understanding the Problem
This is a graph problem dressed up in probability clothes. We have an undirected graph where each edge has a probability (a weight between 0 and 1). When we traverse a path, the total probability is the product of all edge probabilities along the way. We need to find the path from start to end that maximizes this product.
If you've seen Dijkstra's algorithm before, you might already sense the connection. Dijkstra finds the shortest path by minimizing the sum of edge weights. Here, we want to maximize the product of edge weights. The structure is the same, but the "combine" operation changes from addition to multiplication, and the optimization direction flips from minimum to maximum.
There's a neat mathematical trick worth knowing: maximizing a product of probabilities is equivalent to minimizing the sum of their negative logarithms (since log(a * b) = log(a) + log(b)). But we don't actually need to use logarithms. We can directly adapt Dijkstra by using a max-heap instead of a min-heap, and multiplying probabilities instead of adding distances.
Key Constraints:
2 <= n <= 10^4→ Up to 10,000 nodes. This rules out O(n^3) approaches like Floyd-Warshall but keeps O(n^2) or O((V+E) log V) on the table.0 <= edges.length <= 2 * 10^4→ Up to 20,000 edges. The graph is relatively sparse, so adjacency list representation is efficient.0 <= succProb[i] <= 1→ Probabilities are between 0 and 1. Multiplying probabilities never increases the total, so there are no negative-weight-cycle equivalents. This is key because it means Dijkstra-style approaches will work correctly.
Approach 1: Bellman-Ford (Relaxation)
Intuition
The Bellman-Ford algorithm is a classic approach for single-source shortest paths that works by repeatedly relaxing all edges. It doesn't need a priority queue and handles a wider range of graph types than Dijkstra, though it's slower.
For this problem, we flip the relaxation condition. Instead of checking whether going through an edge gives a shorter path (smaller sum), we check whether it gives a more probable path (larger product). We initialize the start node's probability to 1.0 and everything else to 0.0. Then we iterate through all edges up to n-1 times. In each pass, for every edge (u, v) with probability p, if prob[u] * p > prob[v], we update prob[v]. Similarly for the reverse direction since the graph is undirected.
The key optimization: if no probability gets updated during a full pass, we can stop early. This often cuts the runtime dramatically in practice.
Algorithm
- Create a
probarray of sizen, initialized to 0.0. Setprob[start] = 1.0. - Repeat up to
n - 1times:
a. Set a flag updated = false.
b. For each edge (u, v) with probability p:
- If
prob[u] * p > prob[v], setprob[v] = prob[u] * pand markupdated = true. - If
prob[v] * p > prob[u], setprob[u] = prob[v] * pand markupdated = true.
c. If no update occurred, break early.
- Return
prob[end].
Example Walkthrough
Code
- Time Complexity: O(V E). In the worst case, we iterate through all edges V-1 times. With V up to 10^4 and E up to 2 10^4, this is about 2 * 10^8 operations. The early termination optimization usually helps in practice.
- Space Complexity: O(V). We store a probability array of size V.
Each iteration scans every edge, even when most have no chance of improving any probability. What if we used a priority queue to always explore the most probable node first?
Approach 2: Modified Dijkstra's (Max-Heap)
Intuition
Dijkstra's algorithm is the standard tool for shortest paths in graphs with non-negative edge weights. The classic version uses a min-heap to always expand the node with the smallest tentative distance. Our twist: since we're maximizing probability instead of minimizing distance, we use a max-heap and pick the node with the highest tentative probability.
Probabilities are between 0 and 1. Multiplying by any edge weight can only decrease (or maintain) the current probability. This means once we've popped a node from the max-heap, we've already found the best possible probability for it. No future path through other nodes could give a higher probability, because every additional edge only multiplies by something <= 1. This is exactly the same reasoning that makes Dijkstra work with non-negative edge weights.
The early termination when we pop the end node is also correct. Since we process nodes in order of decreasing probability, the first time we pop end is guaranteed to be the maximum probability path.
Algorithm
- Build an adjacency list from the edges and probabilities.
- Create a
probarray of sizen, initialized to 0.0. Setprob[start] = 1.0. - Push
(1.0, start)into a max-heap. - While the heap is not empty:
a. Pop the node curr with the highest probability currProb.
b. If curr == end, return currProb.
c. If currProb < prob[curr], skip (we already found a better path).
d. For each neighbor next with edge probability edgeProb:
- Compute
newProb = currProb * edgeProb. - If
newProb > prob[next], updateprob[next] = newProband push(newProb, next)into the heap.
- Return 0.0 (no path found).
Example Walkthrough
Code
- Time Complexity: O((V + E) log V). Each node is popped from the heap at most once. Each edge is relaxed at most once. Each heap operation takes O(log V).
- Space Complexity: O(V + E). The adjacency list takes O(V + E), plus O(V) for the probability array and heap.