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

LeetCode problem 1514 asks to find the path with the maximum success probability between a start node and an end node in an undirected weighted graph, where each edge has a probability value.

The input consists of the number of nodes n, an edge list, a corresponding probability list, and the start and end indices. If no path exists, the answer should be 0, and an error tolerance of 1e-5 is allowed.

Constraints: 2 ≤ n ≤ 10^4, 0 ≤ start, end < n, start ≠ end, edges length ≤ 2·10^4, each probability between 0 and 1, and at most one edge between any two nodes.

Two example cases illustrate a reachable path with probability 0.25 and an unreachable case returning 0.

Solution analysis: The problem can be solved by a variant of Dijkstra’s algorithm where edge weights are multiplied rather than added. A max‑heap (priority queue) stores nodes with their current best probability, and visited nodes are tracked.

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); // descending order
    }
}
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;
}

The algorithm runs in O(E log V) time and correctly returns the maximum probability or zero when no path exists.