#1514

Medium

LeetCode Problem Workspace

Path with Maximum Probability

Find the path with the highest success probability in a graph from a start node to an end node, using edge probabilities.

array graph heap priority queue shortest path

Problem Statement

You are given a graph with n nodes, each connected by undirected edges with specific success probabilities for traversing each edge. The edge list represents these connections, where each entry [a, b] indicates an undirected edge between nodes a and b, with an associated probability of success stored in the succProb array. Each probability value represents the likelihood that an edge will be successfully traversed.

Given two nodes, start and end, your goal is to find the maximum probability of success for traveling from start to end using the graph. If no path exists between the two nodes, return 0. The answer should be precise to within an error of 1e-5. Note that multiplying probabilities for multiple edges can cause precision errors, which is a key consideration in this problem.

Examples

Example 1

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2

Output: 0.25000

There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.

Example 2

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2

Output: 0.30000

Example details omitted.

Example 3

Input: n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2

Output: 0.00000

There is no path between 0 and 2.

Constraints

2 <= n <= 10^4
0 <= start, end < n
start != end
0 <= a, b < n
a != b
0 <= succProb.length == edges.length <= 2*10^4
0 <= succProb[i] <= 1
There is at most one edge between every two nodes.

Solution Approach

Graph Representation and Priority Queue

To solve this, represent the graph using an adjacency list where each node is connected to other nodes with a probability. A priority queue (max-heap) is used to always expand the node with the highest probability first, similar to Dijkstra's algorithm for shortest paths, but instead of minimizing distance, we maximize the traversal probability.

Algorithm Design

Apply a modified Dijkstra's algorithm to explore the graph. Start by initializing the start node's probability as 1, and for all other nodes, set the probability to 0. Use the priority queue to traverse nodes, updating their probabilities based on the product of the current node's probability and the edge's success probability.

Edge Case Handling

Ensure that edge cases like disconnected nodes or when the start and end nodes are the same are handled properly. If there's no path from the start to the end, return 0. Additionally, handle potential precision issues when multiplying probabilities, as this can introduce small errors in floating-point calculations.

Complexity Analysis

Metric	Value
Time	O((n + m) \cdot \log n)
Space	O(n + m)

The time complexity is O((n + m) * log n), where n is the number of nodes and m is the number of edges, due to the graph traversal with a priority queue. The space complexity is O(n + m) because of the storage required for the graph representation and auxiliary structures such as the priority queue and probability array.

What Interviewers Usually Probe

Check if the candidate uses a priority queue to manage traversal based on probability.
Ensure the candidate accounts for edge case scenarios, such as disconnected nodes or no valid path.
Assess the candidate's understanding of probability and its potential impact on the accuracy of the solution, especially with floating-point operations.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle cases where no path exists between the start and end nodes, leading to incorrect results.
Not accounting for the precision errors when multiplying small probabilities, which can affect the final output.
Misapplying standard shortest-path algorithms without considering the unique nature of the problem, such as maximizing probabilities instead of minimizing distances.

Follow-up variants

What if the graph is directed? How would the solution change?
How would the solution scale for graphs with hundreds of thousands of nodes and edges?
What if the edge weights were not probabilities but costs? Would this become a traditional shortest-path problem?

FAQ

What is the approach for solving the Path with Maximum Probability problem?

You should use a priority queue (max-heap) and a modified Dijkstra's algorithm to maximize the probability of traversing edges from start to end.

How does GhostInterview assist in solving Path with Maximum Probability?

It provides feedback on applying graph algorithms, ensuring correct handling of probabilities and edge cases, and optimizing your solution.

What is the time complexity of the Path with Maximum Probability solution?

The time complexity is O((n + m) * log n), where n is the number of nodes and m is the number of edges in the graph.

Can this problem be solved without a priority queue?

A priority queue is the most efficient approach, but it can be solved with other algorithms like DFS with manual probability tracking, though less efficiently.

What happens if the probabilities multiply to zero?

If the product of probabilities for a path equals zero, it indicates that path is impossible, and the algorithm should return zero for such cases.

terminal

Solution

Solution 1: Heap-Optimized Dijkstra Algorithm

We can use Dijkstra's algorithm to find the shortest path, but here we modify it slightly to find the path with the maximum probability.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

class Solution:
    def maxProbability(
        self,
        n: int,
        edges: List[List[int]],
        succProb: List[float],
        start_node: int,
        end_node: int,
    ) -> float:
        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))
        pq = [(-1, start_node)]
        dist = [0] * n
        dist[start_node] = 1
        while pq:
            w, a = heappop(pq)
            w = -w
            if dist[a] > w:
                continue
            for b, p in g[a]:
                if (t := w * p) > dist[b]:
                    dist[b] = t
                    heappush(pq, (-t, b))
        return dist[end_node]

Continue Practicing

#1368 minimum cost to make at least one valid path in a grid #2290 minimum obstacle removal to reach corner #2577 minimum time to visit a cell in a grid