Solution: Path with Maximum Probability

Explore how to determine the path with the maximum probability between two nodes in an undirected weighted graph. Understand the adaptation of Dijkstra's algorithm with a max heap to maximize traversal probabilities instead of minimizing distances. Learn to build adjacency lists, update probabilities efficiently, and analyze the time and space complexity of the solution. This lesson equips you to solve probabilistic path problems in graph structures effectively.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

Statement

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

Additionally, you are given two nodes, start and end. Your task is to 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.

Constraints:

$2 \leq$ n $\leq 10^3$
$0 \leq$ start, end $<$ n
start $\neq$ ...