北京大学acm暑期课讲义-spfa算法

SPFA算法,SPFA 全称 Shortest Path Faster Algorithm 基本应用为快速求解单源最短路,Spfa算法可以说是Bellman-ford算法的改进版.spfa是利用队列来动态更新最小值.,SPFA算法实现,设Dist代表S到I点的当前最短距离，Fa代表S到I的当前最短路径中I点之前的一个点的编号。开始时Dist全部为+，只有DistS=0，Fa全部为0。 维护一个队列，里面存放所有需要进行迭代的点。初始时队列中只有一个点S。用一个布尔数组记录每个点是否处在队列中。,SPFA算法实现,每次迭代，取出队头的点v，依次枚举从v出发的边v-u，设边的长度为len，判断Distv+len是否小于Distu，若小于则改进Distu，将Fau记为v，并且由于S到u的最短距离变小了，有可能u可以改进其它的点，所以若u不在队列中，就将它放入队尾。这样一直迭代下去直到队列变空，也就是S到所有节点的最短距离都确定下来，结束算法。若一个点最短路被改进的次数达到n ，则有负权环。可以用spfa算法判断图有无负权环,SPFA算法实现,在Bellman-Ford算法中，要是某个点的最短路径估计值更新了，那么我们必须对所有边的终点再做一次松弛操作；在SPFA算法中，某个点的最短路径估计值更新，只有以该点为起点的边指向的终点需要再做一次松弛操作。在极端情况下，后者的效率将是前者的n倍。 在平均情况下，SPFA算法的期望时间复杂度为O(E)。,例题： POJ 2387 POJ 3256,