Problem Description

You have an undirected weighted graph with n nodes (labeled from 0 to n-1). The graph is represented by:

• An edge list edges where edges[i] = [a, b] indicates an undirected edge between nodes a and b
• A probability list succProb where succProb[i] represents the probability of successfully traversing the edge edges[i]

Given a start node and an end node, you need to find the path from start to end that has the maximum probability of success.

The probability of successfully traversing a path is calculated by multiplying the probabilities of all edges along that path. For example, if a path goes through edges with probabilities 0.5, 0.8, and 0.6, the total probability would be 0.5 * 0.8 * 0.6 = 0.24.

Return the maximum probability of successfully reaching the end node from the start node. If no path exists between them, return 0.

Your answer will be considered correct if it differs from the actual answer by at most 1e-5.

Intuition

This problem asks us to find the path with maximum probability, which is essentially finding the "best" path in a weighted graph. This immediately brings to mind shortest path algorithms like Dijkstra's algorithm.

The key insight is that we can adapt Dijkstra's algorithm for this problem. While Dijkstra traditionally finds minimum distances by adding edge weights, here we need to find maximum probabilities by multiplying edge probabilities.

Think about how probabilities work along a path: if we go from node A to B with probability 0.8, and then from B to C with probability 0.5, our total probability is 0.8 * 0.5 = 0.4. Since we're multiplying values between 0 and 1, longer paths generally have lower probabilities (unlike distances which increase).

We can use a greedy approach similar to Dijkstra's: always explore the node we can reach with the highest probability so far. This works because:

1. Probabilities are always between 0 and 1
2. Multiplying by a probability (≤ 1) can never increase the total probability
3. Once we've found the best way to reach a node, exploring it first ensures we find the best paths through it

The algorithm maintains the maximum probability to reach each node from the start. We use a max-heap (priority queue) to always process the most promising node next. When we pop a node from the heap, we know we've found the best way to reach it, and we can use it to potentially improve paths to its neighbors.

The modification from standard Dijkstra is straightforward: instead of adding distances, we multiply probabilities, and instead of finding minimum values, we find maximum values.

Learn more about Graph, Shortest Path and Heap (Priority Queue) patterns.

Solution Approach

We implement a modified Dijkstra's algorithm using a max-heap to find the path with maximum probability.

Step 1: Build the Graph

First, we construct an adjacency list representation of the graph. For each node, we store its neighbors along with the probability of the connecting edge:

g: List[List[Tuple[int, float]]] = [[] for _ in range(n)]
for (a, b), p in zip(edges, succProb):
    g[a].append((b, p))
    g[b].append((a, p))

Since the graph is undirected, we add edges in both directions.

Step 2: Initialize Data Structures

We need:

• A max-heap pq to store nodes with their current maximum probability. Python's heapq is a min-heap, so we store negative probabilities to simulate a max-heap
• A dist array to track the maximum probability to reach each node from the start

pq = [(-1, start_node)]  # Start with probability 1 (stored as -1)
dist = [0] * n
dist[start_node] = 1

Step 3: Process Nodes Using Dijkstra's Algorithm

We repeatedly extract the node with highest probability from the heap:

while pq:
    w, a = heappop(pq)
    w = -w  # Convert back to positive probability

For optimization, we skip processing if we've already found a better path to this node:

if dist[a] > w:
    continue

Step 4: Relax Edges

For the current node a, we check all its neighbors b. If going through a gives a better probability to reach b, we update it:

for b, p in g[a]:
    if (t := w * p) > dist[b]:  # New probability = current prob * edge prob
        dist[b] = t
        heappush(pq, (-t, b))  # Add to heap with negative value

The relaxation condition w * p > dist[b] checks if the path through node a to node b has higher probability than the best known path to b.

Step 5: Return Result

After processing all reachable nodes, dist[end_node] contains the maximum probability to reach the end node from the start node. If the end node is unreachable, this value remains 0.

The algorithm guarantees finding the maximum probability path because:

• We always process nodes in order of decreasing probability from the start
• Once a node is processed with probability p, any future path to it must have probability ≤ p
• The greedy choice of processing highest probability nodes first ensures optimality

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Example Graph:

• Nodes: 0, 1, 2
• Edges: [[0,1], [1,2], [0,2]]
• Probabilities: [0.5, 0.5, 0.2]
• Start: 0, End: 2

This creates a triangle graph where:

• Path 0→1→2 has probability: 0.5 × 0.5 = 0.25
• Path 0→2 has probability: 0.2

Step 1: Build Graph

g[0] = [(1, 0.5), (2, 0.2)]
g[1] = [(0, 0.5), (2, 0.5)]
g[2] = [(1, 0.5), (0, 0.2)]

Step 2: Initialize

pq = [(-1, 0)]  # Start at node 0 with probability 1
dist = [1, 0, 0]  # dist[0]=1, others are 0

Step 3-4: Process Nodes

Iteration 1:

• Pop (-1, 0) from heap → node=0, prob=1
• Check neighbors of node 0:
  • Node 1: 1 × 0.5 = 0.5 > dist[1]=0 ✓ Update
  • Node 2: 1 × 0.2 = 0.2 > dist[2]=0 ✓ Update
• Push (-0.5, 1) and (-0.2, 2) to heap
• State: dist = [1, 0.5, 0.2], pq = [(-0.5, 1), (-0.2, 2)]

Iteration 2:

• Pop (-0.5, 1) from heap → node=1, prob=0.5
• Check neighbors of node 1:
  • Node 0: 0.5 × 0.5 = 0.25 < dist[0]=1 ✗ Skip
  • Node 2: 0.5 × 0.5 = 0.25 > dist[2]=0.2 ✓ Update
• Push (-0.25, 2) to heap
• State: dist = [1, 0.5, 0.25], pq = [(-0.25, 2), (-0.2, 2)]

Iteration 3:

• Pop (-0.25, 2) from heap → node=2, prob=0.25
• Since we reached the end node, we could stop here
• Check neighbors of node 2:
  • Node 1: 0.25 × 0.5 = 0.125 < dist[1]=0.5 ✗ Skip
  • Node 0: 0.25 × 0.2 = 0.05 < dist[0]=1 ✗ Skip
• No updates needed

Iteration 4:

• Pop (-0.2, 2) from heap → node=2, prob=0.2
• Since dist[2]=0.25 > 0.2, skip processing (already found better path)

Step 5: Return Result

• dist[2] = 0.25
• The maximum probability path from 0 to 2 is 0.25 (via path 0→1→2)

The algorithm correctly identified that going through node 1 (0→1→2) with probability 0.25 is better than the direct path (0→2) with probability 0.2.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × log m) where m is the number of edges.

The algorithm uses Dijkstra's algorithm with a min-heap (priority queue) to find the path with maximum probability. The graph construction takes O(m) time to iterate through all edges. In the main algorithm, each edge can be processed at most once (when relaxed), and each relaxation involves a heap push operation which takes O(log k) where k is the current heap size. In the worst case, the heap can contain up to m elements (since each edge relaxation adds an element to the heap), so each heap operation takes O(log m). Since we process at most m edges and perform up to m heap operations, the total time complexity is O(m × log m).

Space Complexity: O(m) where m is the number of edges.

The adjacency list g stores all edges twice (once for each direction in the undirected graph), requiring O(2m) = O(m) space. The priority queue pq can contain at most O(m) elements in the worst case (one entry per edge relaxation). The dist array requires O(n) space. Since in a connected graph n ≤ m + 1, and we need at least n - 1 edges to connect n nodes, the dominant term is O(m). Therefore, the overall space complexity is O(m).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Standard Dijkstra with Addition Instead of Multiplication

A common mistake is treating this as a standard shortest path problem and adding probabilities instead of multiplying them. Since probabilities must be multiplied along a path, the standard Dijkstra's relaxation condition needs modification.

Incorrect approach:

# Wrong: Adding probabilities
new_probability = current_prob + edge_prob

Correct approach:

# Correct: Multiplying probabilities
new_probability = current_prob * edge_prob

2. Precision Loss with Very Small Probabilities

When dealing with many edges, multiplying probabilities can lead to extremely small numbers that may underflow to zero or lose precision. For graphs with many edges, the product of probabilities can become smaller than the machine epsilon.

Solution: Use logarithms to convert multiplication to addition:

# Instead of storing probabilities, store log probabilities
import math

# During initialization
max_log_prob = [float('-inf')] * n
max_log_prob[start_node] = 0  # log(1) = 0

# During relaxation
new_log_prob = current_log_prob + math.log(edge_prob)
if new_log_prob > max_log_prob[neighbor]:
    max_log_prob[neighbor] = new_log_prob
  
# Final result
return math.exp(max_log_prob[end_node]) if max_log_prob[end_node] > float('-inf') else 0

3. Not Handling Disconnected Components

If the start and end nodes are in different connected components, there's no path between them. The code handles this correctly by initializing all distances to 0, but developers might forget to handle this case when modifying the algorithm.

Key insight: The algorithm naturally handles this since unreachable nodes will maintain their initial probability of 0.

4. Forgetting the Optimization Check

Omitting the optimization check if max_probability[current_node] > current_prob: continue won't affect correctness but can significantly impact performance. Without it, the same node might be processed multiple times unnecessarily.

Why it matters: In dense graphs or graphs with many paths, the same node can be added to the priority queue multiple times with different probabilities. Processing outdated entries wastes computation time.

5. Using Min-Heap Incorrectly

Python's heapq is a min-heap, so we need to negate probabilities to simulate a max-heap. A common error is forgetting to negate when pushing or popping from the heap.

Common mistakes:

# Wrong: Forgetting to negate when pushing
heappush(priority_queue, (new_probability, neighbor))

# Wrong: Forgetting to convert back when popping
current_prob = current_prob_neg  # Should be -current_prob_neg

Correct approach:

# Push with negative value
heappush(priority_queue, (-new_probability, neighbor))

# Pop and convert back to positive
current_prob_neg, current_node = heappop(priority_queue)
current_prob = -current_prob_neg