什么是SPFA？SPFA怎么判负环？怎么判正环？
什么是SPFA
SPFA是在Bellman-Ford的基础上进行的一种优化，Bellman-Ford的思路是进行n-1次循环，每次循环都遍历每一条边来更新最短路，复杂度是
O
(
n
∗
m
)
O(n*m)
O(n∗m)，不难发现每次遍历边(u-v)去更新dis[v]时，当且仅当dis[u]被更新过后才会更新dis[v],所以我们可以用个队列，存下来被修改过的点的id，挨个去更新，为了防止进一步优化，我们开一个vi
什么是SPFA
SPFA是在Bellman-Ford的基础上进行的一种优化，Bellman-Ford的思路是进行n-1次循环，每次循环都遍历每一条边来更新最短路，复杂度是
O
(
n
∗
m
)
O(n*m)
O(n∗m)，不难发现每次遍历边(u-v)去更新dis[v]时，当且仅当dis[u]被更新过后才会更新dis[v],所以我们可以用个队列，存下来被修改过的点的id，挨个去更新，为了防止进一步优化，我们开一个vi
共有 0 条评论