城市间Dijkstra最短路径算法Ruby转JS时输出含undefined问题求助

你的代码输出出现undefined的核心原因是JavaScript普通对象无法正确存储引用类型（City实例）作为键。在Ruby中可以直接将City实例作为哈希键，但JS普通对象会把引用类型键自动转为字符串"[object Object]"，导致所有路由被覆盖；遍历for...in拿到的adjacentCity是字符串而非City实例，adjacentCity.name因此返回undefined，最终导致路径回溯时出现缺失值。

具体修复步骤及代码： #

1. 将City类的routes改为Map结构，支持引用类型键
2. 修改addRoute方法，使用Map的set方法添加路由
3. 遍历路由时用Map的entries()方法，正确获取相邻城市实例和价格
4. 处理unvisitedCities为空的边界情况，避免reduce报错

修复后的完整代码：

class City {
  constructor(name) {
    this.name = name;
    // 将routes改为Map结构，支持引用类型作为键
    this.routes = new Map();
  }

  addRoute(city, price) {
    // 使用Map的set方法添加路由
    this.routes.set(city, price);
  }
}

function dijkstraShortestPath(startingCity, finalDestination) {
  let cheapestPricesTable = {};
  let cheapestPreviousStopoverCityTable = {};
  let unvisitedCities = [];
  let visitedCities = {};

  cheapestPricesTable[startingCity.name] = 0;
  let currentCity = startingCity;

  while (currentCity) {
    visitedCities[currentCity.name] = true;
    unvisitedCities = unvisitedCities.filter((city) => city !== currentCity);

    // 使用Map的entries()遍历路由，获取[相邻城市实例, 价格]对
    for (const [adjacentCity, price] of currentCity.routes.entries()) {
      if (!visitedCities[adjacentCity.name]) {
        // 避免重复添加同一城市到未访问列表
        if (!unvisitedCities.includes(adjacentCity)) {
          unvisitedCities.push(adjacentCity);
        }
      }

      const priceThroughCurrentCity = cheapestPricesTable[currentCity.name] + price;
      if (!cheapestPricesTable[adjacentCity.name] || priceThroughCurrentCity < cheapestPricesTable[adjacentCity.name]) {
        cheapestPricesTable[adjacentCity.name] = priceThroughCurrentCity;
        cheapestPreviousStopoverCityTable[adjacentCity.name] = currentCity.name;
      }
    }

    // 处理未访问列表为空的情况，避免reduce报错
    if (unvisitedCities.length === 0) {
      currentCity = null;
    } else {
      currentCity = unvisitedCities.reduce((minCity, city) => {
        return cheapestPricesTable[city.name] < cheapestPricesTable[minCity.name] ? city : minCity;
      }, unvisitedCities[0]);
    }
  }

  const shortestPath = [];
  let currentCityName = finalDestination.name;

  while (currentCityName !== startingCity.name) {
    shortestPath.push(currentCityName);
    currentCityName = cheapestPreviousStopoverCityTable[currentCityName];
  }

  shortestPath.push(startingCity.name);
  return shortestPath.reverse();
}

// 测试代码
let atlanta = new City('Atlanta');
let boston = new City('Boston');
let chicago = new City('Chicago');
let denver = new City('Denver');
let elPaso = new City('El Paso');

atlanta.addRoute(boston, 100);
atlanta.addRoute(denver, 160);
boston.addRoute(chicago, 120);
boston.addRoute(denver, 180);
chicago.addRoute(elPaso, 80);
denver.addRoute(chicago, 40);
denver.addRoute(elPaso, 140);

console.log(dijkstraShortestPath(atlanta, elPaso)); // 输出: ["Atlanta", "Denver", "Chicago", "El Paso"]

额外优化说明： #

在添加城市到unvisitedCities时增加了重复判断，避免同一城市被多次添加到数组中，减少不必要的遍历开销。

内容的提问来源于stack exchange，提问作者Chris Faux