带权有向图最短路径：为何该改进BFS未替代Dijkstra算法？

这个算法在非负边权的有向图中是正确的，但它存在致命的效率缺陷，因此无法替代Dijkstra算法成为首选：

• 时间复杂度过高：Dijkstra算法借助优先队列，结合非负边权的特性，每个节点只会被处理一次（一旦从队列中取出，就确定了该节点的最短路径，无需再重复处理），时间复杂度为O(E log V)（E为边数，V为节点数）。而这个改进版BFS中，同一个节点可能因为多次找到更短路径而被反复加入frontier，最坏情况下时间复杂度会达到O(V*E)，对于大型图来说，这种效率差距是无法接受的。
• 本质是SPFA的变体：这个算法的逻辑和SPFA（Shortest Path Faster Algorithm）类似，都是通过维护待更新的节点集合来松弛路径。但SPFA的优势场景是处理存在负权边但无负环的图，在非负权图中，它的效率远不如专门针对非负权优化的Dijkstra算法。

举个简单的例子：假设存在一条链式路径S→A₁→A₂→…→Aₙ（每条边权重1），同时有一条S直接到Aₙ的边（权重n）。Dijkstra算法处理时，每个节点只会被取出一次，总共O(V log V)的操作；而这个改进BFS会依次处理S、A₁、A₂…Aₙ₋₁，每轮只处理一个节点，循环次数达到O(V)，如果图的规模很大，这种差异会被显著放大。

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