Path with Maximum Probability

Path with Maximum Probability

What is this problem about?

The Path with Maximum Probability problem gives you a graph with probabilistic edge weights (values between 0 and 1). Find the path from start to end that maximizes the probability of success (product of edge probabilities). This coding problem applies Dijkstra-style traversal where you maximize the product instead of minimizing the sum. The shortest path, array, graph, and heap interview pattern is the core.

Why is this asked in interviews?

Samsung, Microsoft, Meta, Amazon, and Google ask this because it tests whether candidates can generalize shortest path algorithms to different objective functions. Maximizing probability products is analogous to minimizing sum distances — the key is using a max-heap and the correct update condition.

Algorithmic pattern used

Modified Dijkstra with max-heap. Initialize prob[start]=1.0, all others=0.0. Use a max-heap of (probability, node). For each node processed: for each neighbor with edge probability p, new_prob = current_prob * p. If new_prob > prob[neighbor], update and push to heap. Return prob[end] when end is processed (or 0 if not reachable).

Example explanation

Nodes=[0,1,2]. Edges: 0-1(0.5), 1-2(0.5), 0-2(0.2). Start=0, End=2.

• Path 0→2: prob=0.2.
• Path 0→1→2: prob=0.5*0.5=0.25. Maximum probability = 0.25.

Common mistakes candidates make

• Using a min-heap (should be max-heap — maximize probability).
• Multiplying when you should add (probabilities multiply on paths).
• Stopping too early before processing the end node.
• Not initializing start probability to 1.0 (multiplicative identity).

Interview preparation tip

Probability path problems are multiplication-based Dijkstra variants. Key transformation: "maximize product" ↔ "minimize negative log" — so you can convert to standard Dijkstra if needed, but a max-heap with probability is more intuitive. Practice adapting Dijkstra to different objective functions: sum, product, max, min. The algorithm structure is the same; only the priority and update condition change.