如何用while循环生成按最近距离排序的环球旅行路线数组

核心实现逻辑 #

• 拆分初始起点与待访问城市列表，每轮迭代从待访问列表中查找距离当前起点最近的城市
• 每完成一段行程后，更新当前起点为刚抵达的城市，同时将该城市从待访问列表中移除
• 通过while循环控制迭代流程，直到所有城市都被纳入行程路线

修改后完整代码 #

const world = [
    [["Start"], [20, 20]],
    [["NY"], [29, 30]],
    [["London"], [24, 27]],
    [["Moscow"], [29, 32]],
    [["Toronto"], [20, 23]]
];

const calcDist2Points = function (p2, p1) {
    const r = 6371;
    let d, dLat, dLon;

    const lat2 = p2[1][0];
    const lon2 = p2[1][1];
    const lat1 = p1[1][0];
    const lon1 = p1[1][1];

    dLat = lat2 - lat1;
    dLon = lon2 - lon1;

    let a =
        Math.sin(dLat / 2) ** 2 +
        Math.cos(lat1) * Math.cos(lat2) * Math.sin(dLon / 2) ** 2;
    let c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
    d = r * c;

    return d; // distance in km
};

const calcDirectRoute = function (input) {
    let tripList = [];
    // 初始化起点与待访问城市列表
    let tempStart = input[0];
    let remainingCities = input.slice(1);

    // while循环：存在未访问城市时持续执行
    while (remainingCities.length > 0) {
        let distances = [];
        // 计算当前起点到所有剩余城市的距离
        for (let i = 0; i < remainingCities.length; i++) {
            distances.push([
                tempStart[0], 
                [tempStart[1][0], tempStart[1][1]], 
                remainingCities[i][0], 
                [remainingCities[i][1][0], remainingCities[i][1][1]], 
                calcDist2Points(remainingCities[i], tempStart)
            ]);
        }

        // 查找距离最短的路线段
        let short = distances[0];
        for (let i = 1; i < distances.length; i++) {
            if (distances[i][4] < short[4]) {
                short = distances[i];
            }
        }

        // 存入行程列表
        tripList.push(short);
        // 更新下一轮的起点为当前抵达的城市
        tempStart = short.slice(2);
        // 从待访问列表中移除已抵达的城市
        remainingCities = remainingCities.filter(city => city[0][0] !== short[2][0]);
    }

    return tripList;
}

console.log(calcDirectRoute(world));

关键修改说明 #

• 新增remainingCities数组存储未访问的城市，初始值为输入数组剔除起点后的所有元素
• 将单次找最近城市的逻辑包裹在while循环中，循环触发条件为remainingCities.length > 0
• 每轮迭代完成后同步更新状态：移除已访问城市、更新当前起点，保证下一轮迭代计算的是剩余城市的距离
• 优化了最短距离查找逻辑，由双重循环改为单次遍历即可找到最小值，运行效率更高

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