图论最短路径之SPFA算法 bellman算法的队列优化

墨蓝 2023-03-01 06:10 5阅读 0赞

#### 一、SPFA算法思想 ####

SPFA算法就是队列优化的[Bellman-Ford算法][Bellman-Ford]，减少了不必要的冗余判断。大致流程是用一个队列来维护，先将源点入队，然后每次从队列首取出一个点，将该点的所有出边（就是以该点为起点的边）松弛，若某条边松弛成功，就将该边的终点入队，重复此过程，直到队列为空结束。

#### 二、代码模板 ####

#include<iostream>
    #include<queue>
    #include<cstring>
    using namespace std;
    const int N = 50,INF = 0x3f;
    
    int e[N],ne[N],h[N],w[N],idx;
    int dis[N],n,m;
    
    void add(int a,int b,int c)	//链式前向星加边模板
    { 
    	e[idx] = b;
    	w[idx] = c;
    	ne[idx] = h[a];
    	h[a] = idx++;
    }
    
    void spfa(int start)
    { 
    	for(int i = 1;i <= n;i++)	//初始化dis数组为无穷大
    		dis[i] = INF;
    	dis[start] = 0;
    	queue<int> q;		//队列q存所有改变了距离的点
    	q.push(start);		//初始化加入起点
    
    	while(!q.empty())
    	{ 
    		int k = q.front();	//取出队首的点并使其出队
    		q.pop();
    		for(int i = h[k];~i;i = ne[i])	//循环所有该点的出边
    		{ 
    			if(dis[e[i]] > dis[k] + w[i])	//若经过该边到终点距离更短，就更新dis数组，并使该点入队
    			{ 
    				dis[e[i]] = dis[k] + w[i];
    				q.push(e[i]);
    			}
    		}
    	}
    }
    
    int main()
    { 
    	int a,b,c;
    	cin >> n >> m;
    	memset(h,-1,sizeof h);	//初始化h数组
    	for(int i = 0;i < m;i++)
    	{ 
    		cin >> a >> b >> c;
    		add(a,b,c);
    	}
    
    	spfa(1);
    
    	for(int i = 1;i <= n;i++)
    		cout << dis[i] << " ";
    
    	return 0;
    }

#### 三、SPFA算法分析 ####

**1、时间复杂度：** 将所有顶点入队一遍的时间复杂度是O(m)，每个顶点入队的平均次数是k，所以spfa的时间复杂度是O(km)，通常情况，k为2左右，所以其时间复杂度比bellman算法低得多。  
**2、spfa判断负权值回路：** 如果一个点入队的次数大于n次，则存在负权值回路。

[Bellman-Ford]: https://blog.csdn.net/qq_45735851/article/details/107492090