Solution: Path with Maximum Probability

Explore how to solve the problem of finding the path with maximum success probability in an undirected weighted graph. Learn to model the graph with adjacency lists and apply a variant of Dijkstra's algorithm that prioritizes probabilities. Understand how to use priority queues to efficiently update paths and analyze time and space complexities relevant to graph processing. This lesson equips you with practical graph traversal techniques applicable to coding interviews and real-world problems.

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$ end
$0 \leq$ a, b $<$ n
a $\neq$ b
...