Path with Maximum Probability
mediumTime: 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).
What must stay true
Probabilities multiply along paths. Max-heap ensures the highest-probability node is processed first.
Easy way to go wrong
Using BFS — that finds fewest edges, not highest probability.