修改BFS替代Dijkstra求解带权无向图最短路径的正确性与复杂度问询

问题1：是否是测试用例有限才通过，算法本身存在逻辑错误？ #

你写的这个算法本质是队列优化的Bellman-Ford算法，也常被称为SPFA（Shortest Path Faster Algorithm），逻辑本身是正确的，能够在无负权环的图上正确计算单源最短路径，并非是测试用例有限才通过。
需要注意两个边界情况：

• 如果图中存在负权环，该算法会因为节点被反复入队陷入死循环，但该题目要求实现Dijkstra，测试用例全部为非负权边的图，不存在负权环，因此可以正常通过。
• 该算法已经不是传统无权图的BFS，你新增的距离松弛逻辑是Bellman-Ford算法的核心特征，和传统仅适用于等权图的BFS有本质区别。

问题2：算法时间复杂度是多少，为什么没有被广泛使用？ #

时间复杂度 #

该算法最坏时间复杂度为O(VE)，其中V是顶点数量，E是边的数量。因为两点之间的最短路径最多包含V-1条边，所以每个节点最多被入队V-1次，每次入队后需要遍历该节点的所有邻接边，最终最坏情况的运算量就是VE级别。

未被广泛使用的原因 #

• 性能稳定性远差于Dijkstra：堆优化的Dijkstra算法时间复杂度稳定为O(ElogV)，在稠密图上比该算法的最坏情况快几个数量级。哪怕是随机非负权图上两者实际运行速度接近，只要遇到专门构造的最坏情况测试用例，该算法的性能会直接退化到和暴力Bellman-Ford一致，生产环境中不可控。
• 适用场景重叠度低：非负权图场景下Dijkstra的稳定性优势压倒性领先，不会选择该算法；只有在处理带负权边的场景下，大家才会考虑用SPFA或者Bellman-Ford，适用范围比Dijkstra窄很多。

内容的提问来源于stack exchange，提问作者Divyam Bhutani