算法简介 SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一种优化,减少了不必要的冗余计算。 它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径,可以处理负边,但判断负回路不方便。 值得注意的是,得到可行解后,可以看成新的约束:xi-xj<=d[i]-d[j],即d[i]为xi-x0的最大值。由此可以看出,SPFA和Bellman-Ford算法解决差分约束系统问题时,实际上是把约束条件强化了,使得满足任意约束条件的值都能构造出一个完整的解。同样的,当约束方程为>=时,求出的xi-xj>=d[i]-d[j],故d[i]为xi-x0的最小值。理解后灵活运用,差分约束问题就比较容易解决了。(这里设x0为源点) 算法流程 SPFA对Bellman-Ford算法优化的关键之处在于意识到:只有那些在前一遍松弛中改变了距离估计值的点,才可能引起他们的邻接点的距离估计值的改变。因此,算法大致流程是用堆栈或队列存放被成功松弛的顶点。初始时,源点s入队。当队列不为空时,取出栈顶/队首顶点,对它的邻接点进行松弛。如果某个邻接点松弛成功,且该邻接点不在堆栈/队列中,则将其入栈/队。经过有限次的松弛操作后,堆栈/队列将为空,算法结束。