图论(三) (一)最短路径算法 4.SPFA算法(1)

今天所说的就是常用的解决最短路径问题最后一个算法，这个算法同样是求连通图中单源点到其他结点的最短路径，功能和Bellman-Ford算法大致相同，可以求有负权的边的图，但不能出现负回路。但是SPFA算法的时间复杂度是O(kE)，k是常数，平均值为2，E是边数。我们可以看到SPFA算法的时间复杂度远远低于Bellman-Ford算法，因此常常选择此算法而不是Bellman算法(虽然其复杂度没有被严格的数学证明)。

简单的说SPFA是将Bellman-Ford算法结合了队列的实现，从而减少了很多冗余的计算。

文字描述如下:初始时将起点加入队列。每次从队列中取出一个元素，并对所有与它相邻的点进行修改，若某个相邻的点修改成功，则将其入队。直到该队列为空时算法结束。

伪代码描述：

dis[i]记录起点s到i的最短路径，m[i][j]记录连接i、j边的长度，pre[v]记录前驱结点。

t[1..n]为队列，头指针是head，尾指针为tail。

布尔数组 e[1..n]记录一个点是否现在存在在队列当中。

初始化：dis[s]=0,dis[v]=∞,memset(e,false,sizeof(e));

起点入队t[1]=s;head=0;tail=1;e[s]=true;

do

{

1.头指针向下移，取出点u。

2.e[u]=false;已经被取出队列。

3.for所有与u相连的点v

if(dis[v]>dis[u]+m[u][v]){

dis[v]=dis[u]+m[u][v];

pre[v]=u;

if(!e[v])// v不在队列中，v入队

{

尾指针下移，v入队;

e[v]=true；

}

}

}while(head<tail);

注意点：

1.因为队列的大小不可知并且容易超过预计，所以采用循环队列的思想，即队列长度不需要开的很大。

2.算法感觉和广搜类似，但是与广搜不同的是，广搜出列的元素不会在入列，而这里会根据需要一直调整队列中的元素。

具体代码将在下一题中运用到，这里就不专门写了。

3.在枚举所有点的那一步中，前提使用邻接表储存的图之后在枚举才行，否则时间复杂度将没有提升。