{x}
blog image

Path with Maximum Probability

You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of traversing that edge succProb[i].

Given two nodes start and end, find the path with the maximum probability of success to go from start to end and return its success probability.

If there is no path from start to end, return 0. Your answer will be accepted if it differs from the correct answer by at most 1e-5.

 

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
Explanation: 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 3:

Input: n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
Output: 0.00000
Explanation: 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 Explanation: Path with Maximum Probability

This problem asks to find the path with the maximum probability of success between two nodes in an undirected weighted graph. The weights represent the probability of successfully traversing an edge. A simple approach using Dijkstra's algorithm, modified to maximize probability instead of minimizing distance, is highly effective.

Algorithm: Modified Dijkstra's Algorithm

Dijkstra's algorithm is a classic for finding the shortest path in a graph. We adapt it here to find the path with the highest probability. The key changes are:

  1. Priority Queue: Instead of a min-heap (to find the smallest distance), we use a max-heap (to find the highest probability). This priority queue stores pairs of (probability, node).

  2. Distance/Probability Array: We maintain an array dist where dist[i] stores the maximum probability of reaching node i from the starting node. Initially, dist[start_node] = 1 (100% probability of being at the start) and all other nodes have probability 0.

  3. Relaxation: The core of Dijkstra's algorithm is the "relaxation" step. For each neighbor b of a node a, we check if the probability of reaching b via a (dist[a] * p(a,b)) is greater than the current probability of reaching b (dist[b]). If it is, we update dist[b] and add b to the priority queue.

  4. Iteration: We repeatedly extract the node with the highest probability from the priority queue, until the queue is empty or we reach the end node.

Time and Space Complexity

  • Time Complexity: The algorithm's runtime is dominated by the priority queue operations. In the worst case, we might process all edges, and each edge addition/removal from the heap takes O(log V) time (where V is the number of nodes). Therefore, the time complexity is O(E log V), where E is the number of edges. Since E can be at most V², the worst-case is O(V² log V). However, it's often much faster in practice, especially for sparse graphs.

  • Space Complexity: The space is used primarily by the priority queue and the dist array. The priority queue can hold at most V elements, and the dist array has size V. Therefore, the space complexity is O(V).

Code Examples

The code examples in Python, Java, C++, Go, and TypeScript implement this modified Dijkstra's algorithm. They all follow the same logic:

  1. Graph Representation: The graph is represented using an adjacency list (or a similar structure).
  2. Initialization: The dist array and priority queue are initialized.
  3. Dijkstra's Algorithm: The main loop extracts the highest-probability node, relaxes its neighbors, and continues until the end node is reached or the queue is empty.
  4. Return Value: The maximum probability of reaching the end_node is returned. If no path exists, the result will be 0.

The use of a max-heap in the priority queue is crucial for correctly finding the path with the maximum probability. The code is well-commented and should be relatively easy to understand. Note the slight variations in syntax and data structures across different programming languages.