Path with Maximum Probability
Problem
Given an undirected weighted graph of n nodes where each edge has a success probability, return the maximum probability of going from start to end. If no path exists, return 0.
n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 20.25import heapq
def max_probability(n, edges, succProb, start, end):
g = [[] for _ in range(n)]
for (u, v), p in zip(edges, succProb):
g[u].append((v, p)); g[v].append((u, p))
best = [0.0] * n
best[start] = 1.0
pq = [(-1.0, start)]
while pq:
neg, u = heapq.heappop(pq)
p = -neg
if u == end: return p
if p < best[u]: continue
for v, w in g[u]:
np = p * w
if np > best[v]:
best[v] = np
heapq.heappush(pq, (-np, v))
return 0.0function maxProbability(n, edges, succProb, start, end) {
const g = Array.from({ length: n }, () => []);
edges.forEach(([u, v], i) => { g[u].push([v, succProb[i]]); g[v].push([u, succProb[i]]); });
const best = new Array(n).fill(0);
best[start] = 1;
const pq = [[1, start]];
while (pq.length) {
pq.sort((a, b) => b[0] - a[0]);
const [p, u] = pq.shift();
if (u === end) return p;
if (p < best[u]) continue;
for (const [v, w] of g[u]) {
const np = p * w;
if (np > best[v]) { best[v] = np; pq.push([np, v]); }
}
}
return 0;
}class Solution {
public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
List<double[]>[] g = new List[n];
for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
for (int i = 0; i < edges.length; i++) {
int u = edges[i][0], v = edges[i][1];
g[u].add(new double[]{v, succProb[i]});
g[v].add(new double[]{u, succProb[i]});
}
double[] best = new double[n];
best[start] = 1.0;
PriorityQueue<double[]> pq = new PriorityQueue<>((a, b) -> Double.compare(b[0], a[0]));
pq.offer(new double[]{1.0, start});
while (!pq.isEmpty()) {
double[] cur = pq.poll();
double p = cur[0]; int u = (int) cur[1];
if (u == end) return p;
if (p < best[u]) continue;
for (double[] nb : g[u]) {
double np = p * nb[1];
if (np > best[(int) nb[0]]) {
best[(int) nb[0]] = np;
pq.offer(new double[]{np, nb[0]});
}
}
}
return 0.0;
}
}double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
vector<vector<pair<int, double>>> g(n);
for (int i = 0; i < (int)edges.size(); i++) {
g[edges[i][0]].push_back({edges[i][1], succProb[i]});
g[edges[i][1]].push_back({edges[i][0], succProb[i]});
}
vector<double> best(n, 0.0);
best[start] = 1.0;
priority_queue<pair<double, int>> pq;
pq.push({1.0, start});
while (!pq.empty()) {
auto [p, u] = pq.top(); pq.pop();
if (u == end) return p;
if (p < best[u]) continue;
for (auto& [v, w] : g[u]) {
double np = p * w;
if (np > best[v]) { best[v] = np; pq.push({np, v}); }
}
}
return 0.0;
}Explanation
Normally Dijkstra finds the path with the smallest summed weight, but here a path's quality is the product of edge probabilities, and we want the largest product. The fix is to run Dijkstra with a max-heap keyed on that running product instead of a min-heap on distance.
We keep best[v] = the highest probability found so far to reach node v. We start with best[start] = 1.0 (a 100% chance of being where we begin) and push (1.0, start) into the heap.
Each step pops the node with the greatest probability. If it is the end, that value is the answer — because we always expand the best candidate first, it is guaranteed optimal. Otherwise we relax each neighbor: np = p * w, and if np > best[v] we improve best[v] and push it.
The check if p < best[u]: continue ignores outdated heap entries. If the heap empties without reaching end, no path exists and we return 0.
Example: edges = [[0,1],[1,2],[0,2]] with probs [0.5,0.5,0.2], start 0, end 2. Going 0 → 1 → 2 yields 0.5 * 0.5 = 0.25, which beats the direct edge 0 → 2 at 0.2, so the answer is 0.25.