JavaScript中findPath()函数求最短路径结果错误问题排查

你的findPath函数目前有两个核心问题导致结果不符合预期，咱们一步步拆解：

1. 数组引用传递导致路径被篡改 #

JavaScript里的数组是引用类型，你在递归中传递的是同一个stack数组的引用。当你执行stack.pop()时，所有之前保存到aSt里的路径（因为都是同一个数组的引用）都会被修改，导致最终存储的路径不完整或错误。

比如当递归找到Isri->Eully->Harith这条路径后，父函数执行stack.pop()会把Harith从数组中移除，导致aSt里的这条路径变成Isri->Eully，完全丢失了目标节点。

2. 提前返回错过更短路径 #

原代码中当找到目标节点时直接return stack，这会终止当前递归分支的后续处理，甚至可能提前结束整个函数。比如你的测试用例中，函数会先处理Isri的第一个邻居Valera，在这个分支里找到一条长路径后直接返回，导致后续的Eully分支（更短的路径）根本没机会被处理。

修复后的代码 #

我调整了逻辑，使用数组副本避免引用问题，同时收集所有可能的路径后再筛选最短的：

function findPath(from, to, stack){
  // 初始化路径，确保每次都是独立数组
  if(!stack) stack = [from];
  var opts = getTravelOptions(from);
  var aSt = [];
  
  for(var i = 0; i < opts.length; ++i){
    const nextNode = opts[i];
    // 跳过已访问节点，避免循环
    if(stack.indexOf(nextNode) >= 0) continue;
    
    // 创建新的路径副本，不修改原stack
    const newStack = [...stack, nextNode];
    
    if(nextNode === to){
      // 找到目标路径，加入结果数组
      aSt.push(newStack);
      continue;
    }else{
      // 递归传递新路径副本
      const news = findPath(nextNode, to, newStack);
      if(news.length > 0){
        aSt.push(news);
      }
    }
    // 不再需要pop，因为用的是新数组副本
  }
  
  // 筛选最短路径
  let shortest = [];
  for(var i2 = 0; i2 < aSt.length; i2++){
    if(shortest.length === 0 || aSt[i2].length < shortest.length){
      shortest = aSt[i2];
    }
  }
  return shortest;
}

function getTravelOptions(from){
  var map = {
    'Sanfew': ['Lisim','Rynir Mines'],
    'Lisim': ['Sanfew','Rynir Mines','Valera'],
    'Valera': ['Endarx','Isri', 'Lisim'],
    'Endarx': ['Rile','Valera'],
    'Rile': ['Endarx'],
    'Isri': ['Valera','Eully'],
    'Eully': ['Isri','Harith'],
    'Harith': ['Eully', 'Port Senyn'],
    'Port Senyn': ['Harith'],
    'Rynir Mines': ['Sanfew','Lisim','Harith']
  };
  if(!from) return Object.keys(map);
  return map[from];
}

关键修改点 #

• 使用数组副本：每次处理下一个节点时，用扩展运算符[...stack, nextNode]创建新的路径数组，确保每个递归分支的路径都是独立的，不会互相干扰。
• 收集所有路径：找到目标节点时，将路径副本加入aSt而不是直接返回，这样能收集所有可能的路径，保证后续能筛选出最短的。
• 移除stack.pop()：因为现在用的是新数组副本，原stack没有被修改，所以不需要再执行弹出操作。

现在调用findPath("Isri","Harith")会返回正确的结果：["Isri", "Eully", "Harith"]

内容的提问来源于stack exchange，提问作者Kyle Boyer