Most Reliable Relay Path
MediumAdvanced Graphs
Problem
A mesh radio network has n relays. Link links[i] = [u, v] (two-way) delivers a message successfully with probability probs[i], independently of other links.
Return the highest probability that a message sent from relay start reaches relay end along a single path. Return 0 if no path exists. Answers within 1e-5 are accepted.
Example 1
- Input:
- n = 4, links = [[0,1],[1,3],[0,2],[2,3]], probs = [0.9,0.5,0.6,0.8], start = 0, end = 3
- Output:
- 0.48
0 → 1 → 3 gives 0.9 · 0.5 = 0.45; 0 → 2 → 3 gives 0.6 · 0.8 = 0.48.
Example 2
- Input:
- n = 3, links = [[0,1]], probs = [0.7], start = 0, end = 2
- Output:
- 0
Example 3
- Input:
- n = 3, links = [[0,1],[1,2],[0,2]], probs = [0.5,0.5,0.2], start = 0, end = 2
- Output:
- 0.25
Constraints
- 2 ≤ n ≤ 10^4
- 0 ≤ links.length ≤ 2·10^4
- 0 ≤ probs[i] ≤ 1
- start ≠ end
Hint
Show the first hint
A path's reliability is a product of numbers in [0, 1]. What happens to it as the path gets longer?
Walkthrough
How to approach it
01Clarify before coding
- Are link failures independent? Yes, so a path's probability is the product of its links.
- Are links two-way? Yes.
- Unreachable end? Return 0.
02Brute force
Enumerate all simple paths from start to end and take the largest product.
Cost: Exponential in the number of relays.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.