先给你划个重点：你写的这段代码不是标准的BFS算法，它其实是SPFA（Shortest Path Faster Algorithm，Bellman-Ford的队列优化版）的简化实现——这就是它能在你的测试案例中得到正确结果的核心原因。咱们一步步拆解：

1. 为啥你的测试案例里这个算法能跑对？ #

你的无向加权图里所有边都是正权重，而且你的代码做了松弛操作：每次发现通过当前节点到邻接点的路径比已记录的更短时，就更新距离，还把邻接点重新塞进队列。这种逻辑刚好能覆盖到最短路径的更新过程——比如从1→4→3→5这条总权重5的路径，会在后续的队列处理中被发现，进而更新节点5的距离，最终得到正确结果。

要是换成标准BFS（每个节点只入队一次，不管权重大小），那肯定出问题：标准BFS会先访问节点2（从1出发，步数1），把它的距离设为2；然后访问节点4（步数1），距离设为1；接着处理节点2时，会把节点5的距离设为2+5=7，节点3的距离设为2+4=6；处理节点4时，发现到节点3的距离是1+3=4，比之前的6小，但标准BFS不会把节点3重新入队，最终节点5的距离会停在7，而不是正确的5。

2. 能不能用这种“类BFS”算法替代Dijkstra？ #

结论：不建议，两者的适用场景和效率差得挺多 #

• 适用场景不一样：
  • Dijkstra专门针对无负权边的图，它用优先队列（最小堆）每次挑当前距离最短的节点处理，保证每个节点只被处理一次（无负权时），时间复杂度是O(E log V)，效率很高，大型图里表现稳定。
  • 你写的这种算法（SPFA）能处理带负权边的图，但如果图里有负权环，它会无限循环（得加额外的检测逻辑）。在无负权边的场景下，它最坏时间复杂度是O(VE)，比Dijkstra慢很多，节点多的时候会很卡。
• 本质逻辑差得远：
  标准BFS靠“所有边权重相同”这个前提，第一次访问节点时的路径就是最短路径；Dijkstra靠优先队列锁定当前最短路径的节点，确保一旦确定了节点的最短距离就不会再改；而你的算法允许节点多次入队、反复更新距离，这是为了处理负权边的情况，但代价是效率下降。

3. 最后总结一下 #

• 你的代码不是标准BFS，是SPFA的简化版，所以能在你的测试案例里得到正确结果；
• 在无负权边的无向加权图里，Dijkstra的效率和稳定性都远优于这种队列式的松弛算法；
• 如果遇到带负权边的图，可以考虑用SPFA或Bellman-Ford，但别忘了要处理负权环的问题。

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