Watch 10 video solutions for Path with Maximum Probability, a medium level problem involving Array, Graph, Heap (Priority Queue). This walkthrough by NeetCodeIO has 18,901 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of traversing that edge succProb[i].
Given two nodes start and end, find the path with the maximum probability of success to go from start to end and return its success probability.
If there is no path from start to end, return 0. Your answer will be accepted if it differs from the correct answer by at most 1e-5.
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 Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.
Example 2:
Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2 Output: 0.30000
Example 3:
Input: n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2 Output: 0.00000 Explanation: There is no path between 0 and 2.
Constraints:
2 <= n <= 10^40 <= start, end < nstart != end0 <= a, b < na != b0 <= succProb.length == edges.length <= 2*10^40 <= succProb[i] <= 1Problem Overview: You are given an undirected graph where each edge has a success probability. Starting from start, reach end with the maximum possible probability by multiplying probabilities along the path. The task is to compute the path whose product of edge probabilities is highest.
Approach 1: Dijkstra's Algorithm with Maximum Product (O(E log V) time, O(V + E) space)
This problem is a variation of the classic shortest path problem. Instead of minimizing distance, you maximize the product of probabilities. Build an adjacency list from the graph, then use a max heap (priority queue) to always expand the node with the highest current probability. Maintain an array where prob[i] stores the best probability found so far for node i. For each popped node, iterate through its neighbors and update their probability if current_prob * edge_prob is larger than the stored value. This greedy expansion works because once a node is processed with the highest probability, no later path can improve it.
Approach 2: Bellman-Ford Algorithm (O(V * E) time, O(V) space)
Bellman-Ford works by repeatedly relaxing all edges. Initialize the start node with probability 1.0 and others with 0. For up to n - 1 iterations, traverse every edge and update both directions: if traveling through one node improves the probability of the other, update it. The multiplication of probabilities replaces the addition used in traditional shortest path problems. This approach is simpler conceptually and does not require a heap, but it scans every edge many times, making it significantly slower for large graphs.
Recommended for interviews: Dijkstra with a max heap is the expected solution. It shows you understand how to adapt classic shortest-path algorithms to maximize products instead of minimizing sums. Bellman-Ford demonstrates the relaxation principle and works as a fallback, but interviewers typically expect the O(E log V) priority queue optimization.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dijkstra's Algorithm with Max Heap | O(E log V) | O(V + E) | Best general solution for weighted graphs when maximizing probability |
| Bellman-Ford Algorithm | O(V * E) | O(V) | Useful when implementing simple edge relaxation without priority queue |