图论最短路径算法（三）SPFA算法（福特/Ford算法的队列实现）

Dear 丶 2021-09-22 23:54 236阅读 0赞

> SPFA是Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算。

### 【算法思想】 ###

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

这个算法，简单的说就是队列优化的bellman-ford，利用了每个点不会更新次数太多的特点发明的此算法。

SPFA 在形式上和广度优先搜索非常类似，不同的是广度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是说一个点修改过其它的点之后，过了一段时间可能会获得更短的路径，于是再次用来修改其它的点，这样反复进行下去。

*算法时间复杂度：O(kE)，E是边数。K是常数，平均值为2。*

### 【算法实现】 ###

dis\[i\]记录从起点s到i的最短路径，w\[i\]\[j\]记录连接i，j的边的长度。pre\[v\]记录前趋。

team\[1…n\]为队列，头指针head，尾指针tail。

布尔数组exist\[1…n\]记录一个点是否现在存在在队列中。

初始化：dis\[s\]=0,dis\[v\]=∞（v≠s），memset(exist,false,sizeof(exist));

起点入队team\[1\]=s; head=0; tail=1;exist\[s\]=true;

//伪代码
        do
        {  
        1、头指针向下移一位，取出指向的点u。
        2、exist[u]=false;已被取出了队列
        3、for与u相连的所有点v          //注意不要去枚举所有点，用数组模拟邻接表存储
                  if (dis[v]>dis[u]+w[u][v])
                     { 
                          dis[v]=dis[u]+w[u][v];
                          pre[v]=u;
                         if (!exist[v]) //队列中不存在v点，v入队。
                           { 
                                        //尾指针下移一位，v入队;
                                      exist[v]=true;
                           }
                     ｝
        }
        while (head < tail);

循环队列：  
采用循环队列能够降低队列大小，队列长度只需开到2\*n+5即可。

### 【例】香甜的黄油(Sweet Butter) ###

**【问题描述】**  
农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1<=N<=500）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。  
农夫John很狡猾。像以前的巴甫洛夫，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。  
农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。  
**【输入格式】**  
第一行: 三个数：奶牛数N，牧场数P（2<=P<=800），牧场间道路数C(1<=C<=1450)。  
第二行到第N+1行: 1到N头奶牛所在的牧场号。  
第N+2行到第N+C+1行：每行有三个数：相连的牧场A、B，两牧场间距（1<=D<=255），当然，连接是双向的。  
**【输出格式】**  
一行 输出奶牛必须行走的最小的距离和.  
另一行 输出最佳牧场编号  
**【输入样例】**  
3 4 5  
2  
3  
4  
1 2 1  
1 3 5  
2 3 7  
2 4 3  
3 4 5

【输出样例】  
8  
4 //说明：放在4号牧场最优  
**【实例程序】**

/** SPEA算法—福特算法的队列实现 dis[i]从s点到i点的最短路径 w[][]权值 a[][num[]],图的存储形式是邻接表 team,队列,head=0,tail=1 exit[],是否在队列中 3 4 5//cow奶牛，pasture牧场，pathCount道路 2 3 4 1 2 1//连接的牧场以及路径长度 1 3 5 2 3 7 2 4 3 3 4 5 */ 
    #include<iostream>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    
    using namespace std;
    const int N = 1000;
    const long maxx = 0x7f;
    int dis[N],a[N][N],num[N],w[N][N],team[N],b[N];
    bool exitt[N];
    int i,j,n,m,cow,pasture,pathCount,u,v,l,head,tail,tot,k;
    long minn; 
    
    int main(){ 
    	cin>>cow>>pasture>>pathCount;
    	memset(b,0,sizeof(b));
    	for(i=1; i<=cow; i++){ 
    		cin>>b[i];
    	} 
    	memset(w,maxx,sizeof(w));
    	memset(num,0,sizeof(num));
    	for(i=1; i<=pathCount; i++){ //初始化图的邻接表 
    		cin>>u>>v>>l;
    		a[u][++num[u]] = v;
    		a[v][++num[v]] = u;
    		w[u][v] = w[v][u] = l;
    	}
    	//算法开始
    	for(i=1; i<=pasture; i++){ //牧场全遍历，寻找路径和最小的牧场 
    		//初始化 
    		memset(dis,maxx,sizeof(dis));
    		memset(team,0,sizeof(team)); 
    		memset(exitt,false,sizeof(exitt)); 
    		head = 0;
    		tail = 1;
    		team[1] = i;//起点入队
    		exitt[i] = true;
    		dis[i] = 0;
    		do{ //遍历队列
    			head ++;
    			head = ((head-1)%100)+1;
    			u = team[head];
    			exitt[u] = false;//u点出队列 
    			for(j=1; j<=num[u]; j++){ //遍历以u为起点的所有邻接边 
    				if(dis[u]+w[u][a[u][j]]<dis[a[u][j]]){ 
    					dis[a[u][j]] = dis[u] + w[u][a[u][j]];
    					if(!exitt[a[u][j]]){ 
    						tail ++;
    						tail = ((tail-1)%100)+1;
    						team[tail] = a[u][j];
    						exitt[a[u][j]] = true;
    					}
    				}
    			}
    		}while(tail != head); 
    		minn = maxx;
    		tot = 0;
    		for(j=1; j<=cow; j++){ //计算以当前节点作为起点到达其他所有节点的最短路径和 
    			tot += dis[b[j]];
    		}
    		if(tot < minn){ 
    			minn = tot;
    			k = i;
    		}
    			
    	} 
    	cout<<"min path long:"<<minn<<endl;
    	cout<<"best pasture:"<<k;
    	return 0;
    	
    	
    	
    	
    }