← DSA Atlas
Dedicated problem page · #1514

Path with Maximum Probability

MediumShortest Path, Dijkstra and Minimum Spanning TreeDijkstra (maximize product)Max-heap on multiplicative weights
Solve on LeetCode ↗
1514
MediumShortest Path, Dijkstra and Minimum Spanning TreeMax-heap on multiplicative weightsDijkstra (maximize product)

Path with Maximum Probability

Given an undirected weighted graph of n nodes where edge i connects edges[i][0] and edges[i][1] with success probability succProb[i], return the maximum probability of a path from start_node to end_node (the product of the edge probabilities along the path). If no path exists, return 0.

Open official problem prompt ↗
In plain English

Compute the single most reliable route from start to end, measured as the product of edge success probabilities.

Picture it like this

Each edge is a relay that forwards a signal with some success chance; you want the chain of relays that gives the signal its best overall chance of arriving intact.

Example
Input
n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start_node = 0, end_node = 2
Output
0.25
Why
Path 0->1->2 gives 0.5 * 0.5 = 0.25, which beats the direct edge 0->2 with probability 0.2.
Constraints
2 <= n <= 10^40 <= edges.length <= 2*10^4edges[i].length == 20 <= a, b < n, a != bsuccProb.length == edges.length0 <= succProb[i] <= 1There is at most one edge between every two nodes
Pattern lesson

See the pattern, then code

Dijkstra (maximize product)
Recognition clue

Single-source best path over non-negative multiplicative weights where you want the maximum product - a Dijkstra variant using a max-heap instead of a min-heap.

↗
Shortest Path, Dijkstra and Minimum Spanning Tree

Shortest paths with non-negative weights or minimum-cost graph connection.. Because probabilities are in [0,1], multiplying by more edges never increases the product, so like Dijkstra with non-negative weights the first time you pop a node you have already found its best probability.

New words, made simpleKnow these before the algorithm
Relaxation
Trying to improve a node's best value using a neighbor's value and the connecting edge.
Max-heap via negation
Python's heapq is a min-heap, so pushing negative probabilities makes the largest come out first.
Multiplicative weight
Path cost is the product, not the sum, of edge weights.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Enumerate all paths (DFS/backtracking)

Blows up on dense graphs; no pruning guarantee.

Explore every simple path and keep the maximum product.

Time ExponentialSpace O(V)
Bellman-Ford style relaxation

Correct but slower than needed for these limits.

Relax all edges up to n-1 times maximizing the product.

Time O(V*E)Space O(V)
Best choiceDijkstra with a max-heap

Optimal for non-negative multiplicative weights.

Always expand the currently most-probable node; the first pop is final because weights are in [0,1].

Time O(E log V)Space O(V + E)
The rule we keep true

Invariant

When a node is popped from the heap, best[node] holds the true maximum probability from the source to that node.

Why this is correct

Reasoning

Multiplying by a probability in [0,1] cannot raise the product, so extending a path never improves it beyond the current best. This monotonicity mirrors non-negative edge weights in classic Dijkstra, guaranteeing the greedy first-pop is optimal.

The algorithm in three movesSay these aloud before coding
1Build an adjacency list of (neighbor, probability)

best=[1.0,0,0], heap=[(-1.0,0)]

2Track best[node], the highest probability found so far, starting at 1.0 for the source

pop 0: push (-0.5,1),(-0.2,2)

3Pop the highest-probability node from a max-heap (store negatives)

pop 1(0.5): 0.5*0.5=0.25>0.2 update best[2]=0.25

4Relax each neighbor: if prob*edge beats best[neighbor], update and push

pop 2 -> return 0.25

5Return best when end_node is popped, else 0

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
00
11
22
1 · Readstart_node=0
2 · Askseed best
3 · Update statebest[0]=1.0, heap=[(-1.0,0)]
4 · ResultSource ready.
Key takeaway

Dijkstra expands node 0, then node 1, upgrading node 2's best probability to 0.25.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 4-8Adjacency with probabilities

    Undirected, so each edge and its probability go both ways.

  2. 2
    Lines 9-11Best array and heap seed

    Source starts at probability 1.0; heap stores negatives for max behavior.

  3. 3
    Lines 13-17Early exit and stale skip

    Returning on end_node pop is safe; skipping when prob < best[u] avoids reprocessing outdated entries.

  4. 4
    Lines 18-22Relaxation

    Only push a neighbor when the multiplied probability strictly improves its recorded best.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • No path between start and end returns 0
  • An edge with probability 0 never improves any best value
  • start_node == end_node returns 1.0 on the first pop
!

Common beginner mistakes

  • Using a min-heap directly finds the least reliable path; you must negate to get a max-heap
  • Comparing sums instead of products - the cost combines multiplicatively
  • Not skipping stale heap entries, which is harmless for correctness but wastes time
Check your understanding

Why is Dijkstra valid here even though we maximize rather than minimize?

More in Shortest Path, Dijkstra and Minimum Spanning Tree

#743Network Delay TimeSingle-source shortest path#332Reconstruct ItineraryEulerian path (Hierholzer's algorithm)#505The Maze IIWeighted shortest path on a grid#778Swim in Rising WaterMinimize the maximum along a path (minimax path)#787Cheapest Flights Within K StopsShortest path with a hop limit#815Bus RoutesUnweighted shortest path (fewest transfers)