Path with Maximum Probability
Medium · Advanced Graphs · Array · Graph · Heap (Priority Queue) · Shortest Path
Problem
You are given an undirected weighted graph with n nodes (0-indexed). edges[i] = [a, b] is an edge whose traversal succeeds with probability succProb[i].
Given start_node and end_node, return the maximum probability that a path from start_node to end_node succeeds, where a path's probability is the product of its edge probabilities. If there is no path, return 0. Answers within 10^-5 of the correct value are accepted.
Examples
Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.8,0.5,0.3], start_node = 0, end_node = 2 Output: 0.4
Going through node 1 succeeds with 0.8 × 0.5 = 0.4, better than the direct 0.3.
Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.8,0.5,0.6], start_node = 0, end_node = 2 Output: 0.6
Now the direct edge, 0.6, beats the two-hop path at 0.4.
Input: n = 3, edges = [[0,1]], succProb = [0.9], start_node = 0, end_node = 2 Output: 0.0
Node 2 has no edges, so no path exists and the answer is 0.
Constraints
- 2 <= n <= 10^4
- 0 <= start_node, end_node < n, start_node != end_node
- 0 <= a, b < n, a != b
- 0 <= succProb.length == edges.length <= 2 * 10^4
- 0 <= succProb[i] <= 1
- There is at most one edge between any two nodes.
Approaches
- Baseline: Bellman-Ford relaxation — time O(n·E), space O(n)
Follow-up
Dijkstra needs only that extending a path never improves it; products of numbers in [0, 1] have that property, so do bottleneck widths. The use cases look for the widest path (maximize the smallest capacity on it) and cap the number of edges, which brings back Bellman-Ford.
Related problems
Start free on Cariara · Coding problems · System design studio
