SPFA算法

SPFA算法的全称是：Shortest Path Faster Algorithm，用来求解负权图最短路。实际上，SPFA算法在国际上通称为“队列优化的Bellman-Ford算法”，仅在中国大陆流行“SPFA算法”的称谓。
SPFA的应用场景：
1、能够计算负权图最短路问题；
2、能够判断是否有负环（即：每跑一圈，路径会减小，所以会一直循环跑下去）。
SPFA在形式上和广度（宽度）优先搜索非常类似，不同的是bfs中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进（重新入队），于是再次用来改进其它的点，这样反复迭代下去。