Pseudo-code:

text
function dfs(node, current_prob, visited):
    if node == end:
        max_prob = max(max_prob, current_prob)
        return

    visited.add(node)
    for neighbor, weight in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, current_prob * weight, visited)
    visited.remove(node)

Why this fails: The time complexity of this brute force approach is roughly $O(N!)$ in the worst case (a complete graph), where $N$ is the number of nodes. With constraints allowing up to $10^4$ nodes, this factorial complexity will immediately result in a Time Limit Exceeded (TLE) error. We need a more efficient approach that avoids re-exploring suboptimal paths.

Core Insight for Path with Maximum Probability

The key intuition for solving LeetCode 1514 efficiently lies in understanding how probabilities behave as path weights.

In a standard shortest path problem (like finding driving distance), edge weights are added, and we seek to minimize the total sum. In this problem, edge weights are probabilities between 0 and 1, and they are multiplied.

Crucially, multiplying by a factor $p$ where $0 \le p \le 1$ always results in a value less than or equal to the original. This property—monotonicity—is analogous to adding positive weights in standard Dijkstra. Because the total probability can only decrease (or stay the same) as we extend a path, we can apply a greedy strategy.

The Strategy: Instead of a Min-Heap (used to find the smallest distance), we use a Max-Heap (Priority Queue). The Max-Heap allows us to always expand the path with the currently highest known probability.

Key Invariant: When we extract a node u from the Max-Heap, we are guaranteed to have found the optimal (maximum probability) path to u. Any other path reaching u later would come from a node with a lower or equal probability and would be multiplied by a factor $\le 1$, resulting in a strictly worse or equal probability. This eliminates the need to visit u again.

Visual Description: Imagine the graph as a network of pipes. We start at the source with full pressure (probability 1.0). As we move through edges, the pressure drops based on the edge's constriction (probability). The algorithm functions like a flood fill that prioritizes the highest-pressure pipes first. The Max-Heap ensures that the "wavefront" of our search always advances from the node that currently retains the most probability, ensuring we don't waste time on paths that have already become too unlikely to be optimal.

Algorithm Strategy: Graph - Shortest Path (Dijkstra's Algorithm)

We will implement a modified version of Dijkstra's Algorithm.

1. Graph Representation: Convert the input edges and succProb arrays into an adjacency list where each node points to a list of pairs (neighbor, probability).
2. Probability Tracking: Maintain an array probs of size n, initialized to 0.0, to store the maximum probability found so far to reach each node. Set probs[start] = 1.0 (100% chance to be at the start).
3. Priority Queue: Use a Max-Heap to store pairs of (current_probability, node). Initially, push (1.0, start).
4. Exploration:
   • While the heap is not empty, pop the node with the highest probability.
   • If this node is the end node, we have found the answer immediately.
   • If the popped probability is less than what is already recorded in probs for that node, skip it (this represents a stale/suboptimal entry).
   • Iterate through all neighbors. Calculate the new probability: new_prob = current_prob * edge_prob.
   • If new_prob is greater than probs[neighbor], update probs[neighbor] and push (new_prob, neighbor) into the Max-Heap.
5. Termination: If the queue empties and we haven't reached end, return 0.0 (path impossible).

Execution Flow

Let's trace the algorithm with a simple example: start=0, end=2. Edges: 0-1 (0.5), 1-2 (0.5), 0-2 (0.2).

1. Initialization:

   • probs array: [1.0, 0.0, 0.0]
   • Max-Heap: [(1.0, 0)]

2. Step 1: Pop (1.0, 0). Current node is 0.

   • Check neighbors of 0:
     • Node 1: new_prob = 1.0 * 0.5 = 0.5. Since 0.5 > probs[1], update probs[1]=0.5, push (0.5, 1).
     • Node 2: new_prob = 1.0 * 0.2 = 0.2. Since 0.2 > probs[2], update probs[2]=0.2, push (0.2, 2).
   • Heap state: [(0.5, 1), (0.2, 2)] (sorted by prob).

3. Step 2: Pop (0.5, 1). Current node is 1.

   • Check neighbors of 1:
     • Node 0: 0.5 * 0.5 = 0.25. 0.25 < probs[0] (which is 1.0). Ignore.
     • Node 2: new_prob = 0.5 * 0.5 = 0.25. Since 0.25 > probs[2] (currently 0.2), update probs[2]=0.25, push (0.25, 2).
   • Heap state: [(0.25, 2), (0.2, 2)].

4. Step 3: Pop (0.25, 2). Current node is 2.

   • Node 2 is the end node.
   • Return 0.25.

Note that the stale entry (0.2, 2) remaining in the heap would be ignored if processed later because its probability is lower than the recorded probs[2].

Proof of Correctness

The correctness of this algorithm relies on the greedy choice property.

Let $P(u)$ be the maximum probability to reach node $u$. When we extract a node $u$ from the priority queue with probability $p$, we assert that $P(u) = p$.

Suppose there exists a different path to $u$ with probability $p' > p$. This path must pass through some node $v$ currently in the priority queue (or already processed) such that the path is $start \to \dots \to v \to \dots \to u$. However, since edge weights $w \le 1$, the probability along a path is non-increasing. Thus, the probability at $v$ must be greater than or equal to $p'$. Since we always extract the maximum value from the heap, we would have processed the path through $v$ before extracting $u$ with probability $p$. This contradiction proves that the first time we extract a node from the Max-Heap, we have found the optimal path.

Reference Implementation

C++ Solution for LeetCode 1514

cpp
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

class Solution {
public:
    double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start_node, int end_node) {
        // Build adjacency list: node -> vector of {neighbor, probability}
        vector<vector<pair<int, double>>> adj(n);
        for (int i = 0; i < edges.size(); ++i) {
            adj[edges[i][0]].push_back({edges[i][1], succProb[i]});
            adj[edges[i][1]].push_back({edges[i][0], succProb[i]});
        }

        // Max-Heap to store {current_prob, node}
        // By default priority_queue is a Max-Heap in C++
        priority_queue<pair<double, int>> pq;
        pq.push({1.0, start_node});

        // Array to store the max probability to reach each node
        vector<double> max_prob(n, 0.0);
        max_prob[start_node] = 1.0;

        while (!pq.empty()) {
            auto [curr_prob, u] = pq.top();
            pq.pop();

            // If we reached the target, return the probability
            if (u == end_node) return curr_prob;

            // Optimization: If current path is worse than what we already found, skip
            if (curr_prob < max_prob[u]) continue;

            for (auto& edge : adj[u]) {
                int v = edge.first;
                double edge_prob = edge.second;
                
                // If a better path is found
                if (curr_prob * edge_prob > max_prob[v]) {
                    max_prob[v] = curr_prob * edge_prob;
                    pq.push({max_prob[v], v});
                }
            }
        }

        return 0.0;
    }
};

Java Solution for LeetCode 1514

java
import java.util.*;

class Solution {
    class Pair {
        int node;
        double prob;
        Pair(int node, double prob) {
            this.node = node;
            this.prob = prob;
        }
    }

    public double maxProbability(int n, int[][] edges, double[] succProb, int start_node, int end_node) {
        // Build adjacency list
        List<List<Pair>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int i = 0; i < edges.length; i++) {
            int u = edges[i][0];
            int v = edges[i][1];
            double p = succProb[i];
            adj.get(u).add(new Pair(v, p));
            adj.get(v).add(new Pair(u, p));
        }

        // Max-Heap using custom comparator
        PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> Double.compare(b.prob, a.prob));
        pq.offer(new Pair(start_node, 1.0));

        // Array to track max probability found so far
        double[] maxProbs = new double[n];
        maxProbs[start_node] = 1.0;

        while (!pq.isEmpty()) {
            Pair curr = pq.poll();
            int u = curr.node;
            double prob = curr.prob;

            if (u == end_node) return prob;

            // Skip stale entries
            if (prob < maxProbs[u]) continue;

            for (Pair edge : adj.get(u)) {
                int v = edge.node;
                double newProb = prob * edge.prob;

                if (newProb > maxProbs[v]) {
                    maxProbs[v] = newProb;
                    pq.offer(new Pair(v, newProb));
                }
            }
        }

        return 0.0;
    }
}

Python Solution for LeetCode 1514

python
import heapq

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:
        # Build adjacency list
        adj = [[] for _ in range(n)]
        for i, (u, v) in enumerate(edges):
            adj[u].append((v, succProb[i]))
            adj[v].append((u, succProb[i]))
        
        # Max-Heap tracked via negative values (since Python has Min-Heap)
        # Store: (-probability, node)
        pq = [(-1.0, start_node)]
        
        # Track max probability for each node
        max_probs = [0.0] * n
        max_probs[start_node] = 1.0
        
        while pq:
            curr_prob_neg, u = heapq.heappop(pq)
            curr_prob = -curr_prob_neg
            
            if u == end_node:
                return curr_prob
            
            # Skip if we found a better path already
            if curr_prob < max_probs[u]:
                continue
            
            for v, edge_prob in adj[u]:
                new_prob = curr_prob * edge_prob
                if new_prob > max_probs[v]:
                    max_probs[v] = new_prob
                    heapq.heappush(pq, (-new_prob, v))
                    
        return 0.0

• Building the adjacency list takes $O(E)$.
• In the worst case, every edge causes an update to the priority queue.
• Each push and pop operation on the heap takes $O(\log V)$ time.
• Therefore, the total time complexity is dominated by the heap operations, resulting in $O(E \log V)$.