Path with Maximum Probability
You are given an undirected weighted graph of n nodes (0-indexed), described by an array of edges where edgesi = [a, b] is an undirected edge connecting a and b with a probability of success of traversing that edge succProbi. Given two nodes start and end, find the path with the maximum probability of success and return that probability, or 0 if there is no path. This is Dijkstra with the comparison flipped : always pop the frontier node with the highest known probability, and relax by multiplying probabilities instead of adding weights.
Constraints
- 2 ≤ n ≤ 104
- 0 ≤ edges.length ≤ 2 × 104
- edgesi.length == 2
- 0 ≤ a, b < n
- a != b
- 0 ≤ succProb.length == edges.length ≤ 2 × 104
- 0 ≤ succProbi ≤ 1
- 0 ≤ start, end < n
- start != end
Example
n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 20.25Explanation The direct edge 0 → 2 succeeds 20% of the time, but the path 0 → 1 → 2 succeeds 0.5 × 0.5 = 25% of the time, which is higher.
Pop the highest-probability node, multiply along each edge
Start at node 0 with probability 1.00.
What happens in this step
prob[0] = 1.00 prob[1] = prob[2] = 0.00 Every node starts unreachable except the source, node 0, which is reached with certainty.
Steps to visualize
- Set the probability of reaching start to 1.00 and every other node to 0.00.
- Repeatedly pop the unfinalized node with the highest known probability.
- Relax its edges: if multiplying through this node beats a neighbor’s current probability, update it.
- Once end is popped, its probability is the answer.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
Start at node 0 with probability 1.00.
What happens in this step
prob[0] = 1.00 prob[1] = prob[2] = 0.00 Every node starts unreachable except the source, node 0, which is reached with certainty.
Solution
function maxProbability(n, edges, succProb, start, end) {
const adj = new Map();
for (let i = 0; i < n; i++) adj.set(i, []);
edges.forEach(([a, b], i) => {
const p = succProb[i];
adj.get(a).push([b, p]);
adj.get(b).push([a, p]);
});
const prob = new Array(n).fill(0);
prob[start] = 1;
const visited = new Set();
while (visited.size < n) {
let current = -1;
let best = -1;
for (let i = 0; i < n; i++) {
if (!visited.has(i) && prob[i] > best) {
best = prob[i];
current = i;
}
}
if (current === -1 || best === 0) break;
visited.add(current); // finalized — never revisited
for (const [neighbor, p] of adj.get(current)) {
const candidate = prob[current] * p;
if (candidate > prob[neighbor]) {
prob[neighbor] = candidate;
}
}
}
return prob[end];
}- Time
- O(n^2 + E)
- Space
- O(n + E)
Test cases
| Input | Expected | Covers |
|---|---|---|
n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2 | 0.25 | example from the docstring |
n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2 | 0 | end is disconnected from start entirely |
n = 2, edges = [[0,1]], succProb = [0.5], start = 0, end = 1 | 0.5 | smallest non-trivial case, one direct edge |
n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.3,0.6], start = 0, end = 2 | 0.6 | the direct edge is better than any multi-hop route |
n = 4, edges = [[0,1],[1,2],[2,3]], succProb = [0.9,0.9,0.9], start = 0, end = 3 | 0.729 | probabilities compound across a longer chain |
n = 2, edges = [[0,1]], succProb = [1], start = 0, end = 1 | 1 | a guaranteed edge carries probability 1 |
n = 4, edges = [[0,1],[1,3],[0,2],[2,3]], succProb = [0.9,0.9,0.2,0.2], start = 0, end = 3 | 0.81 | the two-hop detour beats the alternative two-hop route |