Problem Statement

Path with Maximum Probability

You have a map of places connected by roads. Each road has a number between 0 and 1 that tells you the chance of getting through it safely. You start at one place and want to reach another. Along any route, the chance of success is every road's chance multiplied together. Your job is to find the route with the highest overall chance. Think of it like planning a delivery where each leg of the trip has a survival probability, and you want the safest overall trip. The tool we use is called Dijkstra's algorithm. Dijkstra's is a way of exploring a map by always stepping to the best-so-far place next, like a water flood that reaches the closest spots first. Normally Dijkstra's finds the shortest distance by adding up road lengths and keeping the smallest total. Here we flip it: we multiply chances and keep the biggest total. To always grab the best place next, we use a max-heap. A max-heap is like a basket that always hands you its largest item first, so you never have to dig around for the best option.

mediumGraphGraphsTime: O(E log V) · Space: O(V + E)

Signals to notice

maximum probability pathedge weights are probabilitiesmodified Dijkstra with max-heap

Brute force first

Try all paths — exponential.

The key insight

Max-heap Dijkstra. Probability = product of edges. Start at 1.0. For each neighbor: newProb = current × edge. If better, update. O((V+E) log V).

Trace it on `n=3, edges=[[0,1],[1,2],[0,2]], succProb=[0.5,0.5,0.2], start=0, end=2`

init: dist=[1.0,0,0], heap=[(1.0,0)]  (probs stored as max-heap)
pop (1.0,node0): u≠end; relax 1→0.5, 2→0.2; dist=[1.0,0.5,0.2], heap=[(0.5,1),(0.2,2)]
pop (0.5,node1): u≠end; edge to 0: 0.25<1.0 skip; edge to 2: 0.5*0.5=0.25>0.2 → dist[2]=0.25, push (0.25,2)
heap now=[(0.25,2),(0.2,2)], dist=[1.0,0.5,0.25]
pop (0.25,node2): u==end → return 0.25
(stale (0.2,2) never matters; answer 0.25 = path 0→1→2)

What must stay true

Probabilities multiply along paths. Max-heap ensures the highest-probability node is processed first.

Shape of the loop

build undirected graph; dist[start]=1; maxHeap=[(1.0, start)]
while heap not empty:
  p, u = pop_max(heap)          # highest prob first
  if u == end: return p
  if p < dist[u]: continue       # stale entry
  for (v, w) in graph[u]:
    if p*w > dist[v]: dist[v]=p*w; push(heap, (p*w, v))
return 0.0

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Using BFS — that finds fewest edges, not highest probability.

Graphs Pattern