LeetCode问题＃787“K站内的最便宜航班”。

Question

我正在尝试解决LeetCode问题＃787，"Cheapest Flights Within K Stops"。

"有n个城市通过一些航班相连接。给定一个数组flights，其中flights[i] = [fromi, toi, pricei]表示从城市fromi到城市toi有一条价格为pricei的航班。还给定三个整数src、dst和k，返回从src到dst的最便宜价格，最多经过k个中转站。如果没有这样的路线，则返回-1。"

然而，我在特定的测试用例中遇到了问题：

flights = [[0,1,5],[1,2,5],[0,3,2],[3,1,2],[1,4,1],[4,2,1]], 
n = 5, 
src = 0, 
dst = 2, 
k = 2

预期答案是7，但我的代码返回9。我花了过去的2个小时调试代码，但似乎找不到问题所在。如果有人能指出代码有什么问题，我将非常感激。

代码：

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

    enqueue(node, priority, stopsCount) {
        if(this.isEmpty()) {
            this.nodes.push([node, priority, stopsCount])
        } 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, stopsCount])
                    added = true
                    break;
                }
            }

            if(!added) {
                this.nodes.push([node, priority, stopsCount])
            }
        }
    }

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

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

var findCheapestPrice = function(n, flights, src, dst, k) {
    const graph = {}
    const prices = {}
    for(let i = 0; i < n; i++) {
        graph[i] = []
        if (i == src) {
            prices[i] = 0
        } else {
            prices[i] = Infinity
        }
    }

    for(let [ from, to, price ] of flights) {
        graph[from].push([ to, price ])
    }


    const heap = new minHeap()
    heap.enqueue(src, 0, 0)
    
    while (!heap.isEmpty()) {
        const [ airport, price, stopsCount ] = heap.dequeue()
        
        for (let neighbor of graph[airport]) {
            const [ neighborAirport, neighborPrice ] = neighbor
            const priceToNeighbor = neighborPrice + price
            
            if (prices[neighborAirport] > priceToNeighbor && stopsCount <= k) {
                prices[neighborAirport] = priceToNeighbor
                heap.enqueue(neighborAirport, priceToNeighbor, stopsCount+1)
            }

        }
    }

    
    return prices[dst] == Infinity ? -1 : prices[dst]
};

- Andrew Kim

---

好的，明白了。 - Andrew Kim

好的，明白了。 - Andrew Kim

唯一的解决方案是 k=3 (0 -> 1 -> 4 -> 2 (5+1+1 = 7))，除非我漏掉了什么。你确定这不是一个错误的测试用例吗？另外，对于 k=2，我不知道你的代码是如何得出9的，因为我只能看到一个解决方案 (0 -> 1 -> 2 = 10)，另一条路径 0 -> 3 -> 死胡同 是行不通的。 - Luke Vo

这是因为问题只计算源节点和目标节点之间的节点，所以在路径0 -> 1 -> 4 -> 2中，它只会计算0和2之间的节点，因此不包括1和4。 - Andrew Kim

这是因为问题只计算源节点和目标节点之间的节点，所以在路径0 -> 1 -> 4 -> 2中，它只会计算0和2之间的节点，即1和4。 - Andrew Kim

Answer 1

我没有足够的时间来精确调试出错的地方，但我感觉你的排队优先级有问题。移除这个优化后，程序可以正常工作。

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

    enqueue(node, priority, stopsCount) {
        // This now work without the priority.
        this.nodes.push([node, priority, stopsCount]);
    }

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

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

var findCheapestPrice = function(n, flights, src, dst, k) {
    const graph = {}
    const prices = {}
    for(let i = 0; i < n; i++) {
        graph[i] = []
        if (i == src) {
            prices[i] = 0
        } else {
            prices[i] = Infinity
        }
    }

    for(let [ from, to, price ] of flights) {
        graph[from].push([ to, price ])
    }


    const heap = new minHeap()
    heap.enqueue(src, 0, 0)

    while (!heap.isEmpty()) {
        const [ airport, price, stopsCount ] = heap.dequeue()
        
        for (let neighbor of graph[airport]) {
            const [ neighborAirport, neighborPrice ] = neighbor
            const priceToNeighbor = neighborPrice + price
            
            if (prices[neighborAirport] > priceToNeighbor && stopsCount <= k) {
                prices[neighborAirport] = priceToNeighbor
                heap.enqueue(neighborAirport, priceToNeighbor, stopsCount+1)
            }

        }
    }

    
    return prices[dst] == Infinity ? -1 : prices[dst]
};

const
  flights = [[0,1,5],[1,2,5],[0,3,2],[3,1,2],[1,4,1],[4,2,1]], 
  n = 6, 
  src = 0, 
  dst = 2, 
  k = 2;
console.log(findCheapestPrice(n, flights, src, dst, k));

我尝试将上述代码提交到LeetCode（对此表示抱歉，我并不是有意剽窃，只是想测试一下），它通过了所有的测试用例。

更新：这个修复方法可能会运气好地起作用，尽管我还没有找到反例。实际上，我认为即使没有优先级，它也应该适用于所有情况（请参考下面的评论和其他答案）。即使在这个复杂的图形中，这段代码也能正常工作。

- Luke Vo

---

就像为步数设置一个单独的对象一样，我们可以暂时称之为steps，每次访问节点的邻居时，我们将steps[neighbor]设置为steps[node] + 1。 - Andrew Kim

@גלעדברקן 是的，我同意，就像我之前提到的那样。 - Luke Vo

长度不是我看到的问题。问题在于一个节点的状态可以被设置为比最佳路径所需的状态小的数字。请参阅我的答案。 - גלעד ברקן

这是否有效是因为它实际上是一个广度优先搜索，每个潜在的额外步骤总是添加到队列的末尾？ - גלעד ברקן

@גלעדברקן 是的，这就是为什么。 - Luke Vo

Answer 2

在这个特定的例子中，仅更新和按成本排队的方案不起作用，因为到达机场4的成本在3个站（包括最后一个）之后被设置为5：[0,3,2] -> [3,1,2] -> [1,4,1]。但是为了最优地到达机场2，我们需要中间状态，在那里我们以成本6到达机场4，但是优先级方案阻止了这一点。

[0,1,5] -> [1,4,1]

我不相信Dijkstra算法可以通常用来优化到达目的地的边缘成本，特别是当边的数量受限制时。其他动态规划或图算法可以帮助解决这个问题。

- גלעד ברקן