图论 ——五种最短路算法

时间：2025-04-18 17:12:41

SPFA算法（全称Shortest Path Faster Algorithm）：是Bellman_frod的队优化形式，通常用来求含负权边的的单源最短路问题，以及判断负权环，如果存在负权环就不能用SPFA算法计算最短路

SPFA算法与Bellman_frod的区别：SPFA是Bellman_ford的队优化版，但Bellman_Ford可以用来求负环的最短路，是因为其循环次数是有限制的，因此不会发生死循环，而SPFA算法不可以求带有负环的最短路，由于用了队列存储，只要发生了更新就会不断的入队，因此有了负权回路就不能用SPFA否则会死循环，但是SPFA可以利用这点来判断图中是否存在负环，如果某个点（非终点）的经过边数达到了n就说明存在负环。

时间复杂度：由于SPFA是Bellman_ford优化而来，所以SPFA的最坏的情况是O(n * m)，一般情况下是O（n）

对Bellman_ford的代码优化：

for(int j = 1; j <= n; j ++){        //遍历每个点
	int a = edge[i].a, b = edge[i].b, w = edge[i].w;    //取值
	dist[b] = min(dist[b], back[a] + w);    //松弛操作
}

思路：​​​​​​​采用的是类似BFS无权环的思路，设立一个队列来保存待优化的结点，优化时每次取队头结点t，然后遍历队头能经过的边到达的点v，t点对所能经过的边的点v进行松弛操作，如果能进行松弛操作，并且v点不在当前队列中，就将v点入队，这样不断进行松弛操作，直到队列为空为止

步骤：

  1. 初始化dist[ ]数组，建立一个队列，将起始点入队
  2. 取出队头进行扩展，并进行松弛操作

代码 + 注释：

const int N = 1e5 + 10;        //多少个点
int e[N], ne[N], w[N], idx, h[N];
void add(int a, int b, int c){    //邻接表的存储方式
	e[idx] = b;
	w[idx] = c;
	ne[idx] = h[a];
	h[a] = idx ++;
} 

int spfa(){
	memset(dist, 0x3f3f3f3f, sizeof dist);    //初始化距离
	dist[0] = 1;                        
	queue<int>q;        //定义队列
	(1);
	st[1] = true;
	
	while(()){
		int t = ();        //取出队头
		();
		st[t] = false;
		
		for(int i = h[t]; i != -1; i = ne[i]){    //遍历t能到的点
			int j = e[i];
			if(dist[j] > dist[t] + w[i]){        //松弛操作
				dist[j] = dist[t] + w[i];
				if(!st[j]){
					(j);
					st[j] = true;
				}
			}
		}
	}
	return dist[n];
}

SPFA算法判读负环的代码 + 注释：

const int N = 1e5 + 10;
int dist[N];
int cnt[N];记录当前点t到源点最短路的边数，
bool spfa(){
    // 这里不需要初始化dist数组为 正无穷/初始化的原因是， 如果存在负环， 那么dist不管初始化为多少， 都会被更新
    queue<int>q;

    //不仅仅是第一个点了， 因为第一个点可能到不了有负环的点， 因此把所有点都加入队列
    for(int i = 1;i <= n; i ++){
        (i);
        st[i] = true;
    }

    while(()){
        int t = ();
        ();
        st[t] = false;
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(dist[j] > dist[t] + w[i]){
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;//如果能进行松弛操作就在当前点的cnt+ 1
                if(cnt[j] >= n){
                    return true;
                }
                if(!st[j]){
                    (j);
                    st[j] = true;
                }
            }
        }
    }
    return false;
}

相关文章