如何在给定路线数据中找出从2号站到6号站的最短路径

原代码问题分析 #

你的代码逻辑存在以下几个关键问题：

• 遍历逻辑混乱：直接循环所有路线条目，没有按照从起点出发逐步探索相邻站点的路径逻辑执行，导致错误匹配到反向路线（id:1）
• 访问标记判断错误：!(st2.tostationid in visited) 是检查数组索引而非值是否存在，应该用数组的includes方法判断站点是否已访问
• 路径追踪逻辑错误：没有正确从起点（站点2）开始构建路径，错误引入了无关路线

正确解法：使用BFS寻找最短路径 #

对于无权重的路径搜索，BFS（广度优先搜索）是最适合的算法，它能保证找到最短路径。以下是实现代码：

const routes = [
  { id:1, fromstationid: 1, tostationid: 2 },
  { id:2, fromstationid: 2, tostationid: 1 },
  { id:3, fromstationid: 2, tostationid: 3 },
  { id:4, fromstationid: 3, tostationid: 2 },
  { id:5, fromstationid: 3, tostationid: 4 },
  { id:6, fromstationid: 4, tostationid: 3 },
  { id:7, fromstationid: 3, tostationid: 6 },
  { id:8, fromstationid: 6, tostationid: 3 },
  { id:9, fromstationid: 4, tostationid: 5 },
  { id:10, fromstationid: 5, tostationid: 4 },
  { id:11, fromstationid: 7, tostationid: 6 },
  { id:12, fromstationid: 6, tostationid: 7 }
];

const originId = 2;
const destinationId = 6;

// 构建邻接表，方便快速查找从某站点出发的所有路线
const adjacencyList = {};
routes.forEach(route => {
  if (!adjacencyList[route.fromstationid]) {
    adjacencyList[route.fromstationid] = [];
  }
  adjacencyList[route.fromstationid].push(route);
});

// BFS队列，每个元素保存当前站点和到达该站点的路径
const queue = [[originId, []]];
// 记录已访问的站点，避免循环
const visited = new Set();
visited.add(originId);

let shortestPath = null;

while (queue.length > 0) {
  const [currentStation, path] = queue.shift();
  
  // 如果到达目标站点，记录路径并退出
  if (currentStation === destinationId) {
    shortestPath = path;
    break;
  }
  
  // 遍历当前站点的所有出站路线
  const outgoingRoutes = adjacencyList[currentStation] || [];
  for (const route of outgoingRoutes) {
    const nextStation = route.tostationid;
    if (!visited.has(nextStation)) {
      visited.add(nextStation);
      // 将新路径加入队列
      queue.push([nextStation, [...path, route]]);
    }
  }
}

console.log(shortestPath);

输出结果 #

运行上述代码后，输出与期望一致：

[
  { id: 3, fromstationid: 2, tostationid: 3 },
  { id: 7, fromstationid: 3, tostationid: 6 }
]

代码说明 #

1. 邻接表构建：先将路线数据转换为邻接表，方便快速查找任意站点的所有出站路线
2. BFS队列：队列中的每个元素包含当前站点和到达该站点的完整路径，确保按层级探索，最先到达目标的路径就是最短路径
3. 访问标记：使用Set记录已访问的站点，避免重复探索和循环路径

内容的提问来源于stack exchange，提问作者Amr mahmod