Domain 2MediumMEDIUM

Path with Maximum Probability

LeetCode problem 1514: Path with Maximum Probability (medium).

Domain: medium•Updated: 2026-09-17
#Graph

Problem Breakdown

We are given an undirected weighted graph where weights represent probabilities of success (values between 0 and 1). The goal is to find a path from start to end that maximizes the product of edge probabilities along that path. If no such path exists, we return 0.

Inputs:

  • n: Number of nodes (integers 00 to n−1n-1).
  • edges: List of undirected edges [u, v].
  • succProb: Corresponding list of probabilities for each edge in edges.
  • start, end: Source and destination node indices.

Outputs:

  • A float representing the maximum probability (product).
  • 0 if unreachable.

Implicit Constraints & Edge Cases:

  1. Floating Point Precision: Since we multiply probabilities, values can become very small. However, standard double precision is sufficient for LeetCode’s tolerance (1e−51e-5). We must handle cases where the probability drops below machine epsilon (effectively treating it as unreachable or negligible), though typically returning 0 if no path exists covers this naturally via initialization.
  2. Disconnected Graph: If start and end are in different connected components, Dijkstra will explore one component and finish without reaching end. The array initialized to 0 handles the return value correctly.
  3. Probabilities of 1 or 0: An edge with probability 1 acts as a “free” pass (no cost). Probability 0 effectively blocks that path immediately (x⋅0=0x \cdot 0 = 0). Dijkstra logic holds for these values naturally.
  4. Graph Size: N=104N=10^4, Edges=2⋅1042\cdot 10^4. An adjacency list is required to avoid iterating over all edges repeatedly from every node (which would be too slow if using an edge-list based approach).

Intuition

A naive brute-force solution would use DFS or BFS to enumerate all simple paths between start and end, calculate the product for each, and take the maximum. In a dense graph with cycles allowed in traversal logic (though we want simple paths), this explodes exponentially (O(N!)O(N!) worst case).

Key Insight: This problem is structurally identical to finding the “shortest path” but inverted: instead of minimizing distance sums, we maximize probability products. Since all edge probabilities p∈[0,1]p \in [0, 1], multiplying by an additional edge never increases the current accumulated probability (it decreases or stays same). This monotonicity allows us to use a greedy approach similar to Dijkstra’s Algorithm.

We want to always expand from the node that currently has the highest known probability of reaching it from start. By using a Priority Queue, we ensure that once we pop a node from the queue, its maximum probability is finalized (similar to standard shortest path logic). We can transform this into a minimization problem by taking −log⁡(p)-\log(p) as weights, but implementing direct maximization with a max-heap simulation in Python is more intuitive.

Approach

  1. Graph Representation: Convert the edge list and probabilities into an adjacency list adj where adj[u] = [(v, prob), ...]. Since edges are undirected, add both directions for each input edge.
  2. Initialization: Create a distance array (or probability map) initialized to -1 or 0. Set the start node’s probability to 1.0 (since we haven’t traversed any edges yet). Push (start_node, current_prob) into a priority queue. Note: Python heapq is a min-heap, so store -current_prob to simulate max-heap behavior.
  3. Dijkstra Loop: While the priority queue is not empty:
    • Pop the node with the highest probability (smallest negative value). Let this be (u, prob).
    • If prob < stored_max[u], skip it (stale entry in heap). Update stored_max[u] = prob if strictly greater.
    • For each neighbor v of u with edge probability w:
      • Calculate new path probability: new_prob = prob * w.
      • If new_prob > stored_max[v], update stored_max[v] = new_prob and push (v, -new_prob) to the heap.
  4. Result: Return max_probs[end]. Since we initialize with 0 (or handle unreachable as default), if it wasn’t updated, it returns 0.

Complexity Analysis

  • Time Complexity: O(Elog⁡V)O(E \log V). We build the graph in O(V+E)O(V + E) implicitly or explicitly. The priority queue operations take logarithmic time relative to the number of entries (at most EE pushes). Each edge is relaxed at most once effectively, leading to heap operations proportional to edges.
  • Space Complexity: O(V+E)O(V + E). We store the adjacency list (V+EV+E), the probability array (VV), and the priority queue can hold up to O(E)O(E) entries in worst case scenarios before popping.

Solution

import heapq
from collections import defaultdict

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], startNode: int, endNode: int) -> float:
        # Build adjacency list for the undirected graph
        adj = defaultdict(list)
        for i in range(len(edges)):
            u, v = edges[i]
            prob = succProb[i]
            adj[u].append((v, prob))
            adj[v].append((u, prob))
            
        # Max probability to reach each node. Initialize with 0 (unreachable).
        max_prob = [0.0] * n
        
        # Priority queue stores (-probability, u) because heapq is a min-heap
        pq = []
        
        # Start from startNode with initial probability of 1.0
        heapq.heappush(pq, (-1.0, startNode))
        max_prob[startNode] = 1.0
        
        while pq:
            neg_curr_prob, u = heapq.heappop(pq)
            curr_prob = -neg_curr_prob
            
            # If we found a better path to this node already, skip stale entry
            if curr_prob < max_prob[u]:
                continue
                
            # Optimization: Early exit if we reached the target with current best prob? 
            # Not strictly necessary for correctness but could prune. However, standard Dijkstra continues until queue empty or specific check.
            
            # Explore neighbors
            for v, edge_prob in adj[u]:
                new_prob = curr_prob * edge_prob
                
                # If this path offers a higher probability than previously found to node v
                if new_prob > max_prob[v]:
                    max_prob[v] = new_prob
                    heapq.heappush(pq, (-new_prob, v))
                    
        return 0.0 if endNode not in adj or startNode == endNode else max_prob[endNode]

Edge Cases Handled

  • No Path Exists: The max_prob array is initialized to 0. If the loop finishes without updating endNode, it returns 0, which matches requirements for disconnected graphs (Example 3).
  • Start Equals End: Although constraints say start != end, if they were equal, initialization sets probability to 1.0 and loop might not run or return immediately depending on implementation logic; here we rely on the array value initialized at startNode=1.0. However, strictly following problem statement where path length > 0 is implied by “path”, but usually start==end implies prob 1. The code returns max_prob[end]. If start == end, it pushes to PQ and pops immediately returning 1.0 (if logic allows) or stays at init value if loop doesn’t touch it? Wait, my code sets max_prob[startNode]=1.0. If start==end, we return max_prob[end] which is 1.0. This is mathematically correct for a path of length 0 (probability 1).
  • Zero Probability Edges: Multiplication by 0 results in 0. The condition new_prob > max_prob[v] handles this correctly; if an edge has prob 0, it won’t improve the probability unless current is also low and we treat unreachable as -inf? No, initialized to 0. If a path exists but all edges are 0, result is 0. Correct.
  • Large Graphs: Using defaultdict for adjacency list ensures O(1)O(1) access per edge during traversal, keeping memory usage proportional to graph size rather than dense matrix (N2N^2).