Path with Maximum Probability

Explore how to determine the path with maximum probability in an undirected weighted graph by analyzing node connections and traversal success rates. This lesson helps you understand the problem constraints and apply graph theory concepts to implement efficient algorithms that return the highest probability path between start and end nodes.

We'll cover the following...

Statement
Examples
Understand the problem
Figure it out!
Try it yourself

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$ ...