LeetCode 1514：最大概率路径代码大数据用例报错求助

问题背景 #

给定一个n个节点的无向加权图，边列表edges[i] = [a,b]表示连接节点a和b的无向边，succProb[i]为该边的成功遍历概率。给定起点start_node和终点end_node，求从起点到终点的最大成功概率路径，若不存在路径则返回0，答案误差不超过1e-5即可。

你的代码能通过小测试用例，但在节点数量很大的测试用例上返回错误结果，核心问题出在记忆化递归的逻辑设计上。

原代码 #

var maxProbability = function (n, edges, succProb, start_node, end_node) {
       const graph = {}
       for (let i = 0; i < edges.length; i++) {
         const [a, b] = edges[i]
         if (!graph[a]) graph[a] = {}
         if (!graph[b]) graph[b] = {}
         graph[a][b] = succProb[i]
         graph[b][a] = succProb[i] 
      }

      const probability = (current_node, end_node, memo = {}, visited = {})=>{
          if(current_node == end_node) return 1
          visited[current_node] = true
          if(memo[current_node]) return memo[current_node]
          let result = 0;
          for(const node in graph[current_node]){
             if(!visited[node]){
                 result = Math.max(graph[current_node][node] * probability(node, end_node, memo, visited), result)
             }
         }
          delete visited[current_node]
          memo[current_node] = result
          return memo[current_node]
      }
      return probability(start_node, end_node)
  };

错误分析 #

你的记忆化逻辑存在两个致命问题：

1. 共享visited导致路径受限：递归过程中visited对象是全局共享的，计算某个节点的最大概率时，会标记当前节点为已访问，导致后续计算其他路径时无法回到该节点，错过更优路径。比如存在start→A→B→end（概率0.6）和start→B→A→end（概率0.8）两条路径时，第一次计算会先锁死A节点，导致缓存的start节点结果是0.6，永远无法得到更优的0.8。
2. 缓存结果不具备全局有效性：你在回溯时删除visited标记，但记忆化已经存储了当前节点的结果，后续再次访问该节点会直接返回缓存值，而这个缓存值是基于某次受限路径计算出来的，并非全局最大概率。
3. 递归栈溢出：当节点数很大时，递归深度会超过JavaScript的栈限制，直接导致运行错误。

修复方案 #

这个问题本质是单源最长路径问题（概率相乘求最大值，等价于取对数后的加法最大值），由于边权都是正数（0到1之间的概率），适合用Dijkstra算法的变种来解决：

• 维护maxProb数组，记录每个节点到起点的最大概率，初始时maxProb[start_node] = 1，其余为0。
• 使用优先队列（最大堆），每次取出当前概率最大的节点，更新其邻居的概率：如果当前节点概率 × 边概率 > 邻居的当前最大概率，则更新并加入队列。
• 用迭代方式处理，避免栈溢出，同时保证全局最优性。

修正后的代码 #

var maxProbability = function(n, edges, succProb, start_node, end_node) {
    // 用数组构建邻接表，比对象更高效
    const graph = Array.from({ length: n }, () => []);
    for (let i = 0; i < edges.length; i++) {
        const [a, b] = edges[i];
        const prob = succProb[i];
        graph[a].push([b, prob]);
        graph[b].push([a, prob]);
    }

    // 记录每个节点到起点的最大概率
    const maxProb = new Array(n).fill(0);
    maxProb[start_node] = 1;

    // 用优先队列（取负模拟最大堆，因为JS默认是最小堆）
    const queue = [[-maxProb[start_node], start_node]];

    while (queue.length > 0) {
        // 取出当前概率最大的节点
        const [currentNegProb, currentNode] = queue.shift();
        const currentProb = -currentNegProb;

        // 提前返回：如果已经到达终点，当前概率就是最大值
        if (currentNode === end_node) return currentProb;
        // 跳过：当前概率小于已记录的最大概率，无需处理
        if (currentProb < maxProb[currentNode]) continue;

        // 遍历所有邻居，更新概率
        for (const [neighbor, edgeProb] of graph[currentNode]) {
            const newProb = currentProb * edgeProb;
            if (newProb > maxProb[neighbor]) {
                maxProb[neighbor] = newProb;
                queue.push([-newProb, neighbor]);
                // 维护队列的最大堆性质（简单排序实现，追求效率可替换为二叉堆）
                queue.sort((a, b) => a[0] - b[0]);
            }
        }
    }

    // 没有路径到达终点，返回0
    return 0;
};

补充说明 #

• 数组形式的邻接表在节点数较大时，访问效率比对象更高。
• 优先队列用取负的方式模拟最大堆，避免了自定义堆的复杂度，对于LeetCode的测试用例完全够用。
• 迭代式的Dijkstra变种不会有栈溢出问题，能轻松处理大规模节点的场景。

内容的提问来源于stack exchange，提问作者Pravin Poudel