⚡Flashcard Drill➔
NeetCode #631LC-1514MediumAdvanced Graphs
← Back to All Problems

#631 · #1514 · Path with Maximum Probability(概率最大的路径)

📌 Problem Statement & Constraints

You are given an undirected weighted graph with n nodes, edges and succProb (the success probability of each edge), plus start_node and end_node. Return the maximum probability of reaching end_node, or 0 if unreachable. Constraints: 2 <= n <= 10^4, 0 <= edges.length <= 2 * 10^4, probabilities are in [0, 1].

💡 Core Algorithmic Approaches

  1. This is Dijkstra with a maximising objective and multiplicative edge weights.
  2. Use a max-heap (negated in Python) keyed by the probability so far.
  3. Relax a neighbour when p * w exceeds its current best probability.
  4. The first time the target is popped, its probability is optimal.

💻 Benchmark Python3 Implementation

class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:
        import heapq
        from collections import defaultdict
        g = defaultdict(list)
        for (a, b), p in zip(edges, succProb):
            g[a].append((b, p))
            g[b].append((a, p))
        best = [0.0] * n
        best[start_node] = 1.0
        h = [(-1.0, start_node)]
        while h:
            negp, node = heapq.heappop(h)
            p = -negp
            if node == end_node:
                return p                   # the best path to the target
            if p < best[node]:
                continue                   # a stale heap entry
            for nxt, w in g[node]:
                np_ = p * w                # probabilities multiply
                if np_ > best[nxt]:
                    best[nxt] = np_
                    heapq.heappush(h, (-np_, nxt))
        return 0.0

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(E log V): each edge is relaxed once.
💾 Space Complexity
O(V + E) for the graph.

⚠️ Interview Pitfalls & Follow-ups

  • Using a min-heap: the objective is to maximise the probability.
  • Summing probabilities: independent edges multiply.
  • Using a settled set instead of the best array: with lazy deletion, the stale check is needed.
  • Returning -1 for unreachable: the contract requires 0.0.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems