建议看SPFA前先看看Dijkstra和Bellman-Ford这两个最短路算法。
SPFA的思路比较简单,网上的说法也比较统一,NOCOW和百度百科上都有。这里在网上找到讲的比较通俗易懂的:
*SPFA(Shortest Path Faster Algorithm) *是Bellman-Ford算法的一种队列实现,减少了不必要的冗余计算。 算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素, 并对所有与他相邻的点进行松弛,若某个相邻的点松弛成功,则将其入队。 直到队列为空时算法结束。 它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径,可以处理负边。
SPFA 在形式上和BFS非常类似,不同的是BFS中一个点出了队列就不可能重新进入队列,但是SPFA中 一个点可能在出队列之后再次被放入队列,也就是一个点改进过其它的点之后,过了一段时间可能本 身被改进,于是再次用来改进其它的点,这样反复迭代下去。
判断有无负环:如果某个点进入队列的次数超过V次则存在负环(SPFA无法处理带负环的图)。
SPFA算法有两个优化算法 SLF 和 LLL:
SLF:Small Label First 策略,设要加入的节点是j,队首元素为i,若dist(j)
其他最短路算法:
更多算法可以去看看我的算法专题:
http://www.wutianqi.com/sfzt.html
以下是SPFA的代码模板:
const int INF = 999999;
int map[MAXN][MAXN]; //map[i,j]为初始输入的i到j的距离,未知的map[i,j]=INF;
int dis[MAXN];
char vst[MAXN];
// 参数n表示结点数,s表示源点
int SPFA(int n, int s)
{
// pri是队列头结点,end是队列尾结点
int i, pri, end, p, t;
memset(vst, 0, sizeof(vst));
for(int i=0; i