2019.10.11 Upd：这是 ZS 时期写的一篇非常 naive 的博客，别看了。
SPFA 会被卡，Dij 才最好。
SPFA真是最好的单源最短路算法，没有之一。
SPFA全称是Shortest Path Faster Algorithm，直译过来就是“最短路更快算法”，从这个名称就能看出SPFA效率很高。SPFA加上SLF优化以后被称作单源最短路的“无敌”，时间复杂度可以达到O(ke)（k表示平均每个节点入队次数，k≤2，e表示边数），可以刷负边权。
2019.10.11 Upd：这是 ZS 时期写的一篇非常 naive 的博客，别看了。
SPFA 会被卡，Dij 才最好。
SPFA真是最好的单源最短路算法，没有之一。
SPFA全称是Shortest Path Faster Algorithm，直译过来就是“最短路更快算法”，从这个名称就能看出SPFA效率很高。SPFA加上SLF优化以后被称作单源最短路的“无敌”，时间复杂度可以达到O(ke)（k表示平均每个节点入队次数，k≤2，e表示边数），可以刷负边权。