Maximum Probability Path (LeetCode 1514) – Problem Analysis and Java/C++ Solutions

Recently, a list of ten successful entrepreneurs who once worked at Alibaba was shared online, highlighting the company's talent pipeline.

Among them, Sun Tongyu joined Alibaba's founding team in 1999, created Taobao in 2003, and later served as Taobao President and Alibaba Vice President before leaving in March 2008.

He Xiaopeng co‑founded UC Browser in 2004, which grew to over 400 million users, was later acquired by Alibaba, and subsequently founded Xpeng Motors.

The article then presents today's algorithm problem, LeetCode 1514 “Maximum Probability Path”, of medium difficulty.

Given an undirected weighted graph with n nodes (0‑based) described by edges[i] = [a, b] and success probabilities succProb[i], find the path from start to end that maximizes the product of probabilities, returning 0 if no such path exists.

Example 1: 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 with probability 0.5 × 0.5).

Example 2: n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2 → output 0.00000 (no path).

Constraints: 2 ≤ n ≤ 10⁴, 0 ≤ start, end < n, start ≠ end, 0 ≤ a, b < n, a ≠ b, 0 ≤ succProb.length = edges.length ≤ 2·10⁴, 0 ≤ succProb[i] ≤ 1, at most one edge between any two nodes.

Problem analysis: The task is similar to Dijkstra’s algorithm, but edge weights are multiplied rather than added. A max‑heap (priority queue) stores pairs (node, probability) and always expands the node with the highest current probability. When the end node is popped, its probability is the answer.

Java implementation:

class Pair implements Comparable
{
    int v = 0;
    double p = 0;

    public Pair(int v, double p) {
        this.v = v;
        this.p = p;
    }

    @Override
    public int compareTo(Pair pair) {
        return Double.compare(pair.p, this.p); // sort by probability descending
    }
}

public double maxProbability(int n, int[][] edges, double[] succProb, int start_node, int end_node) {
    List
[] 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];
        int v = edges[i][1];
        double p = succProb[i];
        g[u].add(new Pair(v, p));
        g[v].add(new Pair(u, p));
    }
    boolean[] visited = new boolean[n];
    PriorityQueue
pq = new PriorityQueue<>();
    pq.offer(new Pair(start_node, 1));
    while (!pq.isEmpty()) {
        Pair cur = pq.poll();
        int v = cur.v;
        double p = cur.p;
        if (v == end_node) return p;
        visited[v] = true;
        for (Pair pair : g[v]) {
            if (!visited[pair.v]) {
                pq.offer(new Pair(pair.v, pair.p * p));
            }
        }
    }
    return 0;
}

C++ implementation:

struct Pair {
    int v;
    double p;
    Pair(int v, double p) : v(v), p(p) {}
    bool operator<(const Pair &other) const {
        return p < other.p;
    }
};

double maxProbability(int n, vector
> &edges, vector
&succProb, int start_node, int end_node) {
    vector
> g(n);
    for (int i = 0; i < edges.size(); ++i) {
        int u = edges[i][0];
        int v = edges[i][1];
        double p = succProb[i];
        g[u].emplace_back(v, p);
        g[v].emplace_back(u, p);
    }
    vector
visited(n, false);
    priority_queue
pq;
    pq.emplace(start_node, 1);
    while (!pq.empty()) {
        Pair cur = pq.top();
        pq.pop();
        int v = cur.v;
        double p = cur.p;
        if (v == end_node) return p;
        visited[v] = true;
        for (const auto &pair : g[v]) {
            if (!visited[pair.v]) {
                pq.emplace(pair.v, pair.p * p);
            }
        }
    }
    return 0;
}

At the end of the article, readers are invited to follow the public account for a chance to receive a free book, with details on the giveaway and submission deadline.