SPFA一般O(m)原因 -- 对比SPFA求负环

作者：

zhengyh , 2020-05-31 21:15:10 , 所有人可见 , 阅读 619

2

1

对于有些点，当最短路已经不再变化时, 该点就不需要再入队了, 那么就不是每个点都需要入队n - 1次了, 时间复杂度也就从O(nm)降成了O(m)。
但是对于SPFA求负环来说, 负环上的点的距离能够一直被更新, 所以对于每条边, 环上的点都可能入队n - 1次, 时间复杂度也就是O(nm)了。