算法简介
SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。也有人说SPFA本来就是Bellman-Ford算法，现在广为流传的Bellman-Ford算法实际上是山寨版。
算法流程
算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。 直到队列为空时算法结束。
这个算法，简单的说就是队列优化的bellman-ford,利用了每个点不会更新次数太多的特点发明的此算法
Continue reading “SPFA”