Community Problem

Path with Maximum Probability

Difficulty: Medium

Find the path between two nodes that maximizes the product of edge success probabilities, via modified Dijkstra.

Path with Maximum Probability

Find the path between two nodes that maximizes the product of edge success probabilities, via modified Dijkstra.

MEDIUM

Free

graphs

dijkstra

shortest-path

heap

By @owentanaka

February 28, 2026

Updated May 18, 2026

1,052 views

4.2 (9)

I had this on a Citadel Securities second-round and the interviewer's telltale follow-up was "why does Dijkstra still work even though we are MAXIMIZING a product instead of minimizing a sum?". The answer is that probabilities are in [0, 1], so the product is monotonically non-increasing along a path; replacing min-distance with max-probability and using a max-heap gives you a structurally identical algorithm. The catalog covers Dijkstra basics, but it skipped this product-maximization variant.

Path with Maximum Probability

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 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.

Examples

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.25
Explanation: Two paths: 0 -> 2 with 0.2, or 0 -> 1 -> 2 with 0.5 * 0.5 = 0.25. The latter is higher.

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.3
Explanation: Now the direct edge 0 -> 2 with probability 0.3 beats the two-hop path 0.5 * 0.5 = 0.25.

Example 3:

Input: n = 3, edges = [[0, 1]], succProb = [0.5], start = 0, end = 2
Output: 0
Explanation: Node 2 is unreachable; success probability is 0.

Example 4:

Input: n = 5, edges = [[1, 4], [2, 4], [0, 4], [0, 3], [0, 2], [2, 3]], succProb = [0.37, 0.17, 0.93, 0.23, 0.39, 0.04], start = 3, end = 4
Output: 0.2139 (approximately)
Explanation: Best path is 3 -> 0 -> 4 with probability 0.23 * 0.93 = 0.2139. Other paths (e.g. 3 -> 0 -> 2 -> 4 at 0.23 * 0.39 * 0.17 = 0.0152) are strictly worse.

Constraints

2 <= n <= 10^4.
0 <= start, end < n.
start != end.
0 <= edges.length <= 2 * 10^4.
edges[i].length == 2.
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.

Follow-up

Why does Dijkstra apply when we replace addition with multiplication and minimization with maximization? Because probabilities are in [0, 1], multiplying never INCREASES the value. Greedily picking the highest-probability candidate to relax is sound for the same reason classic Dijkstra is sound: once a node is finalized, no later path can beat it. (Logarithmically, -log(p) for p in (0, 1] is non-negative, so max product is equivalent to min sum of -log(p), which is plain Dijkstra on the transformed graph.)

Solution

JavaScript

Python

Hints

0/4

Hint 1

Hint 2

Hint 3

Hint 4

Solution Walkthrough

Approach: Modified Dijkstra (O((V + E) log V) time, O(V + E) space)

The classical Dijkstra finds the shortest path by minimizing additive distance using a min-heap. Here we MAXIMIZE multiplicative probability instead, so:

Replace min-distance with max-probability.
Replace currentDist + edgeWeight relaxation with currentProb * edgeWeight.
Replace the min-heap with a max-heap (or negate keys when using Python's heapq).

Everything else, including the early-stop "if we pop the end node, return immediately" trick, transfers verbatim.

Algorithm

Build adjacency list mapping node -> [(neighbor, probability)].
Allocate best[0..n-1] = 0; set best[start] = 1.
Initialize max-heap with (1, start).
While the heap is non-empty:
- Pop the highest-probability entry (prob, u).
- If u == end, return prob.
- If prob < best[u], the entry is stale; skip it.
- For each neighbor v with edge weight w: if prob * w > best[v], update best[v] and push.
If the loop ends without reaching end, return 0.

Why It Works

The correctness of Dijkstra's greedy relies on edge weights NOT decreasing the path metric in a way that lets a future node "undo" the metric. With probabilities in [0, 1] and multiplication, every edge multiplies the running product by a number <= 1, so the product is non-increasing along a path. The max-heap pops the highest-probability frontier entry, and once we pop u we know no path through any later-popped node can produce a higher probability for u. This is the same argument as classic Dijkstra, just inverted.

Alternatively: take weight' = -log(probability). Now weight' >= 0 and the goal is min sum(weight'), which is exactly classic Dijkstra. The two formulations produce identical results.

Complexity

Sample

Text

n=3, edges=[[0,1],[1,2],[0,2]], succProb=[0.5, 0.5, 0.2], start=0, end=2
adj[0] = [(1, 0.5), (2, 0.2)]
adj[1] = [(0, 0.5), (2, 0.5)]
adj[2] = [(0, 0.2), (1, 0.5)]
Heap pops (1, 0): relax 1 -> 0.5, 2 -> 0.2.
Heap pops (0.5, 1): relax 2 -> 0.25 (better than 0.2).
Heap pops (0.25, 2): u == end, return 0.25.

Text

Metric  Value
Time    O((V + E) log V) since each node is pushed at most a few times
Space   O(V + E) for the adjacency list and heap

Pitfalls

Using BFS instead of Dijkstra. BFS treats every edge as weight 1, which is wrong here; the answer would be the path with the FEWEST edges, not the highest probability.
Skipping stale heap entries. When we update best[v], the OLD heap entry for v (with lower probability) is still in the heap. When we later pop a stale entry, the prob < best[u] guard discards it. Without that guard, the algorithm is correct but does extra work.
Forgetting to negate for Python's heapq. Python's heapq is a min-heap. Negate the probability when pushing (and again when reading), or use a custom heap.

Solution Code

All Problems