BFS 与最短路算法（Dijkstra）的区别

一句话结论

BFS 就是"所有边权为 1 的 Dijkstra"；Dijkstra 就是"带权图上的 BFS"。 两者的骨架完全相同——"从近到远逐层确定距离"——区别只在：扩展顺序用什么数据结构、以及这个顺序为什么成立。

相同点

• 都求单源最短路（在各自的适用范围内）；
• 都基于同一个核心事实："先被确定"的节点的距离就是最终答案，每个节点只确定一次；
• 在无权图上，BFS 和 Dijkstra 的行为完全一致。

不同点

	BFS	Dijkstra
数据结构	普通队列（FIFO），先进先出	优先队列（小根堆），按当前距离
扩展顺序	按层（步数）：第 k 层所有节点先于第 k+1 层	按当前已知最短距离
适用边权	所有边权相等（通常为 1）	任意非负权
正确性依赖	边权相同 ⇒ 先到的一定更优，队列顺序就是距离顺序	非负权 ⇒ 一旦出堆距离确定，后续不可能更短（贪心）
复杂度	$O(V+E)$	$O((V+E)\log V)$（堆优化）
判重时机	入队时标记 vis	出堆时标记 vis（或入堆时，写法不同）

为什么 BFS 在带权图上会错

反例（边权非负但不同）：

a --100--> b
a ---1---> c
c ---1---> b

BFS 从 a 出发：第 1 层同时访问 b、c，于是认为 dist[b] = 100（直达）并标记 b 已访问；第 2 层从 c 到达 b 时距离为 1+1=2，但因为 b 已经被访问过而被跳过。结果 BFS 给出 100，正确答案是 2。

根因：BFS 用"步数"当距离，队列保证的是"步数少的先处理"；而带权图中"步数少"不等于"距离短"。先到先得的性质被破坏，vis 就失效了。

为什么 Dijkstra 不能处理负权边

Dijkstra 的贪心是：从堆中弹出的节点，其距离已经不可能再被更新。这个结论依赖"所有边权 ≥ 0"——任何绕路都会增加距离，所以当前最短的直接路径不可能被一条更长的路径超越。

有负权边时贪心失败：可能"先绕远路、再通过负权边回来"反而更短，而那时节点早已出堆定案。

a---3---b
|       |
4___c__-2

（Bellman-Ford / SPFA 用"松弛 N-1 轮"处理负权，代价是 $O(EV)$，见 21_shortest_path。）

什么时候"用 BFS 当最短路"是对的

只要所有边权相等，BFS 就是正确且最快的单源最短路算法。典型场景：

• 网格/迷宫类题（上下左右移动代价都是 1）——BFS 是对的，不是"因为地图是二维的"，而是因为每次移动代价相同；
• 单位权图（如 847 状态压缩 BFS，见 09_bfs_dfs）；
• 0-1 BFS：边权只取 0 或 1 时，用双端队列替代优先队列——0 边插队头、1 边插队尾，仍保持 $O(V+E)$。可以看作"只差一个档位的 Dijkstra"。

决策速查

1. 边权相等（1 或 0/1）→ BFS / 0-1 BFS（最快）；
2. 边权非负但不全相等 → Dijkstra；
3. 有负权、无负环 → Bellman-Ford / SPFA；
4. 有负环 → 无解，但可用 BF/SPFA 检测出来；
5. 全源最短路 → Floyd（$O(V^3)$，或对每个源跑一次 1/2/3）。

关系图：BFS ⊂ 0-1 BFS ⊂ Dijkstra ⊂ Bellman-Ford。每一步都是放宽"边权"限制、同时付出更高的复杂度代价。