Path with Maximum Probability
Problem
n nodes. Edge edges[i] = [a, b] can be
crossed successfully with probability succProb[i]. A path succeeds only if every
edge on it succeeds, so its probability is the product of its edge probabilities.
Return the highest success probability of any path from start_node to
end_node, or 0 if they are not connected (answers within
1e-5 are accepted).n=3, edges=[[0,1],[1,2],[0,2]], succProb=[0.5,0.5,0.2], start=0, end=2Output0.25n=3, edges=[[0,1],[1,2],[0,2]], succProb=[0.5,0.5,0.3], start=0, end=2Output0.3n=3, edges=[[0,1]], succProb=[0.5], start=0, end=2Output0.02 ≤ n ≤ 104 · 0 ≤ edges.length ≤ 2·104 · 0 ≤ succProb[i] ≤ 1 · at most one edge per pair · start ≠ end
Try it yourself
class Solution {
public double maxProbability(int n, int[][] edges, double[] succProb, int start_node, int end_node) {
}
}
[0, 1] can never increase the
value — the mirror image of adding a non-negative weight. So Dijkstra works unchanged
if you use a max-heap and “relax” with multiplication.Instinct Weighted edges plus "minimum cost, time or effort to reach" - grab a min-heap and always expand the cheapest unsettled node next (Dijkstra).
Memory hack Pop the cheapest, skip the stale, relax the rest - Dijkstra is a ripple in a pond that touches near shores before far ones.
Open the Shortest Paths guide →Approaches
Brute ForceBellman-Ford Relaxation
O(V · E)Space O(V)Set best[start] = 1. In each round, relax every edge in both
directions: best[v] = max(best[v], best[u] × p). A best path uses at
most V-1 edges, so V-1 rounds suffice; stop early once a
round changes nothing.
public double maxProbability(int n, int[][] edges, double[] succProb, int start_node, int end_node) { double[] best = new double[n]; best[start_node] = 1.0; for (int round = 0; round < n - 1; round++) { boolean changed = false; for (int i = 0; i < edges.length; i++) { int a = edges[i][0], b = edges[i][1]; double p = succProb[i]; if (best[a] * p > best[b]) { best[b] = best[a] * p; changed = true; } if (best[b] * p > best[a]) { best[a] = best[b] * p; changed = true; } } if (!changed) break; // nothing improved: values are final } return best[end_node]; }
Simple and needs no adjacency list, but can sweep all edges V times.
BetterQueue-Based Relaxation (SPFA)
O(V · E) worst, much less on averageSpace O(V + E)Only nodes whose value just improved can improve their neighbours. Keep those nodes in a FIFO queue (with an in-queue flag) and relax only their edges, instead of re-scanning the entire edge list each round.
public double maxProbability(int n, int[][] edges, double[] succProb, int start_node, int end_node) { List<List<double[]>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); for (int i = 0; i < edges.length; i++) { adj.get(edges[i][0]).add(new double[]{edges[i][1], succProb[i]}); adj.get(edges[i][1]).add(new double[]{edges[i][0], succProb[i]}); } double[] best = new double[n]; boolean[] inQueue = new boolean[n]; Deque<Integer> queue = new ArrayDeque<>(); best[start_node] = 1.0; queue.add(start_node); inQueue[start_node] = true; while (!queue.isEmpty()) { int u = queue.poll(); inQueue[u] = false; for (double[] e : adj.get(u)) { int v = (int) e[0]; double cand = best[u] * e[1]; if (cand > best[v]) { best[v] = cand; if (!inQueue[v]) { queue.add(v); inQueue[v] = true; } } } } return best[end_node]; }
Skips useless work in practice, but its worst case is still Bellman-Ford's.
OptimalDijkstra with a Max-Heap
O((V + E) log V)Space O(V + E)Always expand the node with the highest known probability. Because every
edge multiplies by at most 1, no later path can beat it, so its value is final the
first time it is popped. Return as soon as end_node is popped.
public double maxProbability(int n, int[][] edges, double[] succProb, int start_node, int end_node) { List<List<double[]>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); for (int i = 0; i < edges.length; i++) { adj.get(edges[i][0]).add(new double[]{edges[i][1], succProb[i]}); adj.get(edges[i][1]).add(new double[]{edges[i][0], succProb[i]}); } double[] best = new double[n]; best[start_node] = 1.0; // Max-heap on probability: entries are {probability, node} PriorityQueue<double[]> pq = new PriorityQueue<>((x, y) -> Double.compare(y[0], x[0])); pq.add(new double[]{1.0, start_node}); while (!pq.isEmpty()) { double[] top = pq.poll(); int u = (int) top[1]; if (top[0] < best[u]) continue; // stale entry if (u == end_node) return top[0]; for (double[] e : adj.get(u)) { int v = (int) e[0]; double cand = top[0] * e[1]; if (cand > best[v]) { best[v] = cand; pq.add(new double[]{cand, v}); } } } return 0.0; }
Each node is finalised once; the early exit often avoids exploring the graph.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Bellman-Ford Relaxation | O(V · E) | O(V) |
| Better | Queue-Based Relaxation (SPFA) | O(V · E) worst, much less on average | O(V + E) |
| Optimal | Dijkstra with a Max-Heap | O((V + E) log V) | O(V + E) |
- Using a min-heap out of habit — you want the largest probability first.
- Adding edges in only one direction — the graph is undirected.
- Comparing doubles with
==in tests — use a small tolerance.
- Justify Dijkstra: multiplying by p ≤ 1 is monotone, like adding a weight ≥ 0.
- Mention the −log transform to connect it to standard shortest paths.
- Point out the early return when the target is popped.