Problem 26.4 · Shortest PathsMedium

Path with Maximum Probability

What it teaches: Dijkstra with a max-heap and multiplication.

Practise it on judges as “Path with Maximum Probability”.

The problem

Undirected edge i joins edges[i] with success probability succProb[i]. Return the maximum probability of reaching end from start (0 if unreachable).

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

Constraints

2 ≤ n ≤ 10⁴
0 ≤ p ≤ 1

Pattern clues in the wording

→ Maximise a product of values ≤ 1

These clues point to Dijkstra's Shortest Path: Always expand the closest unfinished node from a min-heap; with non-negative weights, its distance is final.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        return 0.0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	n = 3 edges = [[0,1],[1,2],[0,2]] succProb = [0.5,0.5,0.2] start = 0 end = 2	0.25
2	n = 3 edges = [[0,1],[1,2],[0,2]] succProb = [0.5,0.5,0.3] start = 0 end = 2	0.3
3	n = 3 edges = [[0,1]] succProb = [0.5] start = 0 end = 2	0

From slow to fast

Approaches

1. Max-heap Dijkstra · O(E log V)

Max-heap Dijkstra

Time O(E log V) Space O(V + E)

prob[start] = 1. Pop the largest probability; relax neighbours with prob × p.

Approach 1

import java.util.*;

class Solution {
    public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        List<List<double[]>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int i = 0; i < edges.length; i++) {
            adj.get(edges[i][0]).add(new double[]{edges[i][1], succProb[i]});
            adj.get(edges[i][1]).add(new double[]{edges[i][0], 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[] t = pq.poll();
            int u = (int) t[1];
            if (u == end) return t[0];
            if (t[0] < best[u]) continue;
            for (double[] e : adj.get(u)) {
                int v = (int) e[0];
                double p = t[0] * e[1];
                if (p > best[v]) { best[v] = p; pq.offer(new double[]{p, v}); }
            }
        }
        return 0.0;
    }
}

Verdict: Same algorithm, flipped comparison.

Before you submit

Edge cases and common mistakes

Test these inputs

Unreachable end (0)
Probability 0 edges

Mistakes people make

Using a min-heap.

Interview

Follow-up questions

How could you reuse standard (sum-based) Dijkstra?

Command Palette

The problem

Approaches

Max-heap Dijkstra

Edge cases and common mistakes

Follow-up questions