AlgoMaster Logo

Path with Maximum Probability

mediumFrequency6 min readUpdated June 23, 2026

Understanding the Problem

This is a shortest-path problem stated in terms of probability. We have an undirected graph where each edge carries a probability between 0 and 1. The probability of a full path is the product of the probabilities of its edges, since the events of successfully traversing each edge are independent. We want the path from start to end whose product is the largest.

This maps onto Dijkstra's algorithm. Dijkstra finds the shortest path by minimizing the sum of edge weights. Here we maximize the product of edge weights. The structure is the same; the combine operation changes from addition to multiplication, and the optimization direction flips from minimum to maximum.

The two problems are formally equivalent. Maximizing a product of probabilities is the same as minimizing the sum of their negative logarithms, because log(a * b) = log(a) + log(b) and the logarithm of a value in (0, 1] is non-positive. We will not use logarithms here, though. Adapting Dijkstra directly, with a max-heap and multiplication, is simpler and avoids the floating-point error that taking logs would introduce.

Key Constraints:

  • 2 <= n <= 10^4 → Up to 10,000 nodes. An all-pairs method like Floyd-Warshall would be O(n^3), around 10^12 operations, which is too slow. A single-source method that runs in O((V + E) log V) is the right scale.
  • 0 <= edges.length <= 2 * 10^4 → Up to 20,000 edges. The graph is sparse (E is close to V, not V^2), so an adjacency list is the efficient representation.
  • 0 <= succProb[i] <= 1 → Multiplying by any edge probability can only keep a path probability the same or lower it. Extending a path never improves it, which is the analogue of non-negative edge weights and is what lets a greedy Dijkstra-style approach work correctly.

Approach 1: Bellman-Ford (Relaxation)

Intuition

Bellman-Ford finds single-source shortest paths by repeatedly relaxing every edge. It needs no priority queue, just a probability array and a loop over the edge list.

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 set the start node's probability to 1.0 and everything else to 0.0, then iterate over 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 set prob[v] = prob[u] * p, and we apply the same check in the reverse direction because the graph is undirected.

Why n-1 passes suffice: a shortest path in a graph with n nodes uses at most n-1 edges, and each pass extends every best-known path by one more edge. After n-1 passes, every reachable node holds its final value. If a full pass produces no update, all paths have stabilized and we can stop early.

Algorithm

  1. Create a prob array of size n, initialized to 0.0. Set prob[start] = 1.0.
  2. Repeat up to n - 1 times:
    • Set a flag updated = false.
    • For each edge (u, v) with probability p:
      • If prob[u] * p > prob[v], set prob[v] = prob[u] * p and mark updated = true.
      • If prob[v] * p > prob[u], set prob[u] = prob[v] * p and mark updated = true.
    • If no update occurred, break early.
  3. Return prob[end].

Example Walkthrough

1Initialize: prob[start=0] = 1.0, all others = 0.0
0
1
start
1
0
2
0
1/6

Code

Each pass rescans every edge, including the many that cannot improve any probability. The next approach replaces the blind rescanning with a priority queue that always expands the most probable node first, which lets each node be finalized exactly once.

Approach 2: Modified Dijkstra's (Max-Heap)

Intuition

Dijkstra finds shortest paths in graphs with non-negative edge weights by using a min-heap to always expand the node with the smallest tentative distance. Here we maximize probability instead of minimizing distance, so we use a max-heap and expand the node with the highest tentative probability. Each edge multiplies the running probability rather than adding to a running distance.

Algorithm

  1. Build an adjacency list from the edges and probabilities.
  2. Create a prob array of size n, initialized to 0.0. Set prob[start] = 1.0.
  3. Push (1.0, start) into a max-heap.
  4. While the heap is not empty:
    • Pop the node curr with the highest probability currProb.
    • If curr == end, return currProb.
    • If currProb < prob[curr], skip (we already found a better path).
    • For each neighbor next with edge probability edgeProb:
      • Compute newProb = currProb * edgeProb.
      • If newProb > prob[next], update prob[next] = newProb and push (newProb, next) into the heap.
  5. Return 0.0 (no path found).

Example Walkthrough

1Initialize: prob[start=0]=1.0, heap=[(1.0, 0)]
0
1
start
1
0
2
0
1/6

Code