Path with Maximum Probability
mediumTime: O(E log V)Space: O(V + E)
Recognize the pattern
maximum probability pathedge weights are probabilitiesmodified Dijkstra with max-heap
Brute force idea
Try all paths — exponential.
Better approach
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).
Key invariant
Probabilities multiply along paths. Max-heap ensures the highest-probability node is processed first.
Watch out for
Using BFS — that finds fewest edges, not highest probability.