01 普通图论中求最短路 - 五种基础求解最短路的算法

如果是相同边权求最短路，可以直接使用 $BFS$

最短路一共分为四个部分， 分别为 无负权单源最短路 ， 无负权多源最短路 ， 含负权单源最短路 ， 含负权多源最短路

稠密图一般选择邻接矩阵建图， 稀疏图一般选择链式前向星

无负权

单源最短路

迪杰斯特拉 - 朴素版

时间复杂度 ： $O(n^2)$ , 适用于稠密图
同时可以用来建最短路树 $SPT$

vi dis(n + 1, INF), vis(n + 1);
 
dis[s] = 0;
rep(i, 1, n){
	int x = -1;
	rep(j, 1, n) 
		if(!vis[j] && (x == -1 || dis[j] < dis[x]))  
			x = j;
	
		vis[x] = 1;
		
		rep(j, 1, n)
			if(!vis[j] && dis[x] + a[x][j] < dis[j]) 
				dis[j] = dis[x] + a[x][j];
}

迪杰斯特拉 - 堆优化版

时间复杂度 ： $O((n+m)(logn))$ ， 适用于稀疏图
空间复杂度 ： $O(n+m)$

int n, m, s;
void solve(){
    cin>>n>>m>>s;
    vector<pair<int,int>> G[n+10];
 
    rep(i,1,m){
        int a,b,c;cin>>a>>b>>c;
        G[a].push_back({b,c});
    }
 
    vi dis(n + 10, INF); //记录 1 到这个 点 的最短距离
    vi vis(n + 10); //记录这个点是否出圈，也就是是否已经到 到这个点 的最短路径
    dis[s] = 0;
 
    priority_queue <pair<int, int>> q;  //优先队列，现存的最短路
    q.push({0, s});
    while(q.size()){
        auto x = q.top();
        q.pop();
        int a = -x.first;  
        int b = x.second;  
        if(vis[b])continue;//到达这个点的最短的最短路径已经求了 //这个点已经不用再去找了
 
        vis[b] = 1;//遍历这个点之前将 b 标记为 1，表明到达b点的最短路径已经找过了 
        
        for(auto v : G[b]){//从 b 点可以到哪些点
            if(dis[v.first] > dis[b] + v.second){//试图更新到 v 点的最短路径
                dis[v.first] = dis[b] + v.second;
                q.push({-dis[v.first], v.first});//将这个新的最短路径和点放进去
            }
        }
    }
 
    rep(i,1,n){
        if(dis[i] == INF){
            cout<<tmp-1<<(i==n?endl:" ");
        }else{
        cout<<dis[i]<<(i==n?endl:" ");}
    }
    return;
}

多源最短路

Floyd

跑 n 次迪杰斯特拉的时间复杂度 ： $O(nmlogn)$
动态规划思想
主要用于点比较少，然后一次性将所有点之间的最短路都求出来
时间复杂度 ： $O(n^3)$

vii dis(n + 1, vi(n + 1, INF)), p(n + 1, vi(n + 1));
 
rep(i, 1, n) dis[i][i] = 0;
 
void floyd(){
	rep(k, 1, n){ //核心思想: i 经过 k 到 j 的最短路
 		rep(i, 1, n){
			rep(j, 1, n){
				if(dis[i][j] > dis[i][k] + dis[k][j]){
					dis[i][j] = dis[i][k] + dis[k][j];
					p[i][j] = k; //插点
				}
			}
		}
	}
}
 
void path(int i, int j){ // i -> j 的路径经过了哪些点，按照路径输出
	if(p[i][j] == 0) return;
	int k = p[i][j];
	path(i, k);
	cout << k << endl;
	path(k, j);
}

含负权

• 需要区分题目是让你找最短路还是负权环！
• 最短路可以选择 $SPFA$ , 负权环只有 贝尔曼 可以处理

单源最短路

贝尔曼

• 处理含有边权为负数的最短路径
• 可以找到全部的负权环

时间复杂度 ： $O(nm)$
空间复杂度 ： $O(n+m)$
下面的代码主要为枚举每个点的出边
但是如果题目当中 $n$ 和 $m$ 相差不大，意味着这是一个稀疏图，那么我们可以在 $rep(i,1,n)$ 里面枚举每条边，时间复杂度 $O(nm)$ ，但是实际运行时间会小得多

第 $n$ 轮还被更新的点，说明达到这个点存在负环

vector<pair<int,int>> G[N];//记录有向边和边权
vi dis(n+10，INF);//记录最短路径
 
dis[1] = 0;
 
int flag=0;//判断每次循环是否有松弛操作发生，若没有发生，说明所有点的最短路径都已经找到，可以跳出循环。 如果循环结束的时候松弛操作还是发生了，说明存在负环，（也就是这个点的最短路径是负数且存在环，不断地循环重复路径，会让这个最短路径越来越小。
rep(i,1,n){
	flag = 0;
	rep(j, 1, n){
		if(dis[j] == INF)continue;//说明这个点还没有到达过，用这个点去更新没有意义
		
		for(auto v:G[j]){
			if(dis[v.first] > dis[j] + v.second){
				flag = 1;
				dis[v.first] = dis[j] + v.second;
			}
		}
	}
	
	if(flag == 0)break;
}
if(flag == 1) cout<<"存在负环"<<endl;
	
rep(i,1,n)cout<<(dis[i]==INF?-1:dis[i])<<" \n"[i==n];

SPFA

时间复杂度 ： 最坏情况下 $O(nm)$

vector<pair<int,int>> G[N]; //记录有向边和边权
vi dis(n + 10，INF); //记录最短路径
vi cnt(n + 10); //记录边数
vi vis(n + 1);
dis[s] = 0; 
vis[s] = 1;
queue<int> q;
q.push(s);
 
while(!q.empty()){
	int u = q.front();
	q.pop();
	vis[u] = 0;
	for(auto v : G[u]){
		if(dis[u] + v.second < dis[v.first]){
			dis[v.first] = dis[u] + v.second;
			cnt[v] = cnt[u] + 1;
			if(cnt[v] >= n) //表示存在负环，然后跳出这一整个程序
			if(vis[v.first] == 0) q.push(v.first);
			vis[v.first] = 1; 
		}
		
	}
}
 
如果没有前面跳出，那就相当于没有负环	
rep(i,1,n)cout<<(dis[i]==INF?-1:dis[i])<<" \n"[i==n];

多源最短路

Jphnson 算法

用于求存在负边权全源最短路，但是 无法找全所有的负权环
核心思想：
建造一个 0 号点

vector<pii> G[n + 1];
vi vis(n + 1), cnt(n + 1), h(n + 1), dis(n + 1);
 
void spfa(){
	queue<int> q;
	fill(vis.begin(), vis.end(), 0);
	fill(h.begin(), h.end(), INF);
	h[0] = 0, vis[0] = 1;
	q.push(0);
	
	while(!q.empty()){
		int u = q.front();
		q.pop();
		vis[u] = 0;
		
		for(auto x : G[u]){
			int v = x.first;
			int w = x.second;
			if(h[v] > h[u] + w){
				h[v] = h[u] + w;
				cnt[v] = cnt[u] + 1;
				if(cnt[v] > n){
					exit(0); //存在负权环
				}
				if(vis[v]) continue;
				q.push(v);
				vis[v] = 1;
			}
		}
	}
}
 
//求原点 s 到各个点的最短路
void dijkstra(int s){ 
	priority_queue<pii> q;
	fill(dis.begin() + 1, dis.end(), INF);
	fill(vis.begin(), vis.end(), 0);
	dis[s] = 0;
	q.push({0, s});
	while(!q.empty()){
		int u = q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(auto x : G[u]){
			int v = x.first;
			int w = x.second;
			if(dis[v] > w + dis[u]){
				dis[v] = w + dis[u];
				if(!vis[v]) q.push({-dis[v], v});
			}
		}
		
	}
}
 
void solve(){
 
	//输入
	
	rep(i, 1, n) G[0].push_back({i, 0});
 
	spfa();
	rep(u, 1, n){
		for(auto &x : G[u]){
			x.second += h[u] - h[x.first];
		}
	}
	rep(i, 1, n){
		dijkstra(i);
		rep(j, 1, n){
			if(dis[j] != INF) dis[j] = dis[j] + h[j] - h[i];
		}
	}
	return;
}