为何「K站内最便宜航班」问题使用BFS而非Dijkstra算法？

为什么允许重复访问节点的BFS能找到K站内的最优路径？ #

这个问题的核心约束是最多经过k个中转站，对应路径的边数最多为k+1条（每经过一个站对应一段航班）。这里的BFS并非传统意义上的“按距离分层”，而是按中转次数（路径边数）分层遍历：

• 第0层（中转0次）：仅包含起点src，代价为0。
• 第1层（中转1次）：遍历所有从src直飞的节点，记录到达这些节点的代价。
• 第i层（中转i次）：遍历所有从第i-1层节点出发能到达的节点，更新到达目标节点的代价——如果当前路径的总价比之前记录的更低，就更新，哪怕该节点之前已经被访问过。

我们需要维护一个数组dist，其中dist[u]表示当前到达节点u的最低代价。在每一层遍历中，我们只保留当前中转次数下的最优代价，后续如果有相同中转次数但代价更高的路径到达同一节点，直接跳过；如果中转次数更少但代价更高，也不影响最终结果——因为我们要找的是所有中转次数≤k的路径中的最小值，只要遍历完所有允许的层数，dist[dst]就是答案。

这种重复访问节点的操作是必要的：比如可能存在一条中转次数更少但代价更高的路径，和一条中转次数更多但代价更低的路径，只有允许重复访问，才能覆盖到后者并更新最优代价。

当k设为无穷大时，BFS能否替代Dijkstra算法求全局最优路径？ #

绝对不能。

Dijkstra算法的核心是优先队列（小顶堆）驱动的贪心策略：每次弹出当前代价最低的节点，一旦某个节点被弹出队列，我们就确定了到达该节点的最短路径，后续再遇到该节点可以直接忽略，这保证了算法的效率和正确性。

而普通BFS（基于普通队列）不具备这种优先级筛选能力：

1. 效率问题：即使所有边权为正，普通BFS可能先处理代价更高的路径，导致后续发现更低代价路径时，已经对该节点做了大量不必要的后续遍历。比如从src到A有两条路径：直接飞代价100，经B中转代价50，但需要2条边。普通BFS会先处理src→A，记录代价100，之后才处理src→B→A并更新代价为50——如果图规模很大，这种重复处理会导致时间复杂度飙升。
2. 环的问题：如果图中存在正权环，普通BFS会陷入无限循环，因为它没有机制判断某个节点是否已经找到了最优路径；而Dijkstra算法一旦确定节点的最短路径，就不会再处理该节点的后续路径。
3. 负权边问题：如果图中有负权边，普通BFS完全无法处理，而Dijkstra本身也不支持负权边，但这不是BFS的优势——处理负权边需要Bellman-Ford或SPFA算法。

当k无穷大时，问题转化为无限制的最短路径问题，此时普通BFS无论是效率还是正确性都远不如Dijkstra算法。

总结 #

• 在LeetCode 787的k站限制场景下，BFS的有效性来自按中转次数分层+维护节点当前最低代价，确保所有允许范围内的路径都被评估，且保留最优解。
• 无中转次数限制时，普通BFS无法替代Dijkstra，因为它缺乏贪心优先级筛选，会导致效率低下甚至逻辑错误。

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