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
- This is Dijkstra with a maximising objective and multiplicative edge weights.
- Use a max-heap (negated in Python) keyed by the probability so far.
- Relax a neighbour when
p * wexceeds its current best probability. - 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.