LeetCode #787至多K站中转最便宜航班代码调试求助

你的代码核心问题在于误用了普通Dijkstra算法处理带中转次数限制的最短路径问题。普通Dijkstra只维护每个节点的全局最低价格，但忽略了中转次数的约束——即使到达某个节点的价格不是最低的，只要中转次数更少，后续就可能在允许的中转次数内到达终点，得到更优的总价格。

以你的测试用例为例：

• 路径0→3→1→4的价格是5，但需要3次航班（中转2次），后续再飞4→2就会超过k=2的中转限制（变成3次中转）。
• 路径0→1→4的价格是6，但只需要2次航班（中转1次），后续飞4→2刚好是3次航班（中转2次），总价格7，这才是符合要求的最优解。

但你的代码因为0→3→1→4的价格更低，更新了prices[4]为5，导致处理0→1→4时，因为价格6比5高，直接跳过了这条路径，从而无法得到后续的最优解。

修复方案 #

我们需要修改算法，允许同一节点在中转次数未超限的情况下，即使价格稍高也被处理。可以通过记录每个节点在不同航班数下的最低价格来实现（航班数=中转次数+1，k次中转对应最多k+1次航班），或者改用更适合处理步数限制的Bellman-Ford算法。

修改后的代码（基于Dijkstra的优化） #

class minHeap {
    constructor() {
        this.nodes = []
    }

    enqueue(node, priority, flightsCount) {
        if(this.isEmpty()) {
            this.nodes.push([node, priority, flightsCount])
        } else {
            let added = false;
            for(let i = 0; i < this.nodes.length; i++) {
                if(this.nodes[i][1] > priority) {
                    this.nodes.splice(i, 0, [node, priority, flightsCount])
                    added = true;
                    break;
                }
            }
            if(!added) {
                this.nodes.push([node, priority, flightsCount])
            }
        }
    }

    dequeue() {
        return this.nodes.shift()
    }

    isEmpty() {
        return this.nodes.length === 0
    }
}

var findCheapestPrice = function(n, flights, src, dst, k) {
    const graph = {}
    // 二维数组：dist[airport][flightsCount] 表示用flightsCount次航班到达airport的最低价格
    const dist = Array.from({length: n}, () => Array(k+2).fill(Infinity))
    for(let i = 0; i < n; i++) {
        graph[i] = []
    }
    for(let [ from, to, price ] of flights) {
        graph[from].push([ to, price ])
    }

    // 初始状态：0次航班到达src，价格0
    dist[src][0] = 0
    const heap = new minHeap()
    heap.enqueue(src, 0, 0)
    
    while (!heap.isEmpty()) {
        const [ airport, price, flightsCount ] = heap.dequeue()
        
        // 如果当前价格已经不是该航班数下的最低价格，直接跳过
        if (price > dist[airport][flightsCount]) continue;
        
        // 最多允许k+1次航班（对应k次中转）
        if (flightsCount > k) continue;
        
        for (let neighbor of graph[airport]) {
            const [ neighborAirport, neighborPrice ] = neighbor
            const newPrice = price + neighborPrice
            const newFlightsCount = flightsCount + 1
            
            // 如果新路径的价格更低，更新并入堆
            if (newPrice < dist[neighborAirport][newFlightsCount]) {
                dist[neighborAirport][newFlightsCount] = newPrice
                heap.enqueue(neighborAirport, newPrice, newFlightsCount)
            }
        }
    }

    // 取所有允许的航班数下到达dst的最低价格
    const minPrice = Math.min(...dist[dst])
    return minPrice === Infinity ? -1 : minPrice
};

关键修改点 #

1. 用二维数组dist记录每个节点在不同航班数下的最低价格，避免覆盖掉中转次数更少的路径。
2. 增加判断：如果当前弹出的价格已经不是该航班数下的最低价格，直接跳过，减少无效处理。
3. 明确航班数限制：最多允许k+1次航班（对应题目要求的k次中转）。
4. 最终取所有允许航班数下到达目的地的最低价格。

更简洁的Bellman-Ford实现 #

如果不需要使用堆，Bellman-Ford算法更适合这类带步数限制的问题，代码更简洁：

var findCheapestPrice = function(n, flights, src, dst, k) {
    let prices = Array(n).fill(Infinity)
    prices[src] = 0
    
    // 进行k+1次松弛（对应最多k+1次航班）
    for (let i = 0; i <= k; i++) {
        // 复制当前价格，避免本轮更新影响其他节点
        let tempPrices = [...prices]
        for (let [from, to, price] of flights) {
            if (prices[from] !== Infinity) {
                tempPrices[to] = Math.min(tempPrices[to], prices[from] + price)
            }
        }
        prices = tempPrices
    }
    
    return prices[dst] === Infinity ? -1 : prices[dst]
};

Bellman-Ford的思路是：每次迭代更新所有边，模拟一次航班的飞行，最多迭代k+1次（对应k次中转），这样就能保证只考虑中转次数不超过k的路径。

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