Most Reliable Path Between Two Services
Each network link succeeds with a known probability. A request routed along a path succeeds only if every link on it succeeds. Find the path from a start service to an end service that maximizes the overall success probability.
Problem
Given n nodes and an undirected edge list edges where edge i connects edges[i] = [a, b] with success probability succProb[i], return the maximum probability of success to travel from start to end. If there is no path, return 0.
Input
An integer n, edges as [a, b] pairs, a parallel array succProb, and integers start and end.
Output
A floating-point number: the maximum path success probability.
Constraints
- 2 <= n <= 10^4
- 0 <= edges.length <= 2*10^4
- 0 <= succProb[i] <= 1; at most one edge per pair.
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
Path 0->1->2 gives 0.5*0.5 = 0.25, better than the direct 0.2.
Example 2
Input
n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
Output
0.00000
No path connects 0 to 2.