一.多源最短路：Floyed算法

简介

        可以处理带有负权边的图，但不能处理带有负环的图。

        时间复杂度:O()

模板

#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);//优化
	int n,m;//节点数与边数
	cin>>n>>m;
	int a[n+5][n+5];//a[i][j]代表i节点到j节点的最短路径
	memset(a,0x3f,sizeof(a));//初始化
	for(int i=1;i<=n;i++){ a[i][i]=0; }//每个节点到自身的最短路径均为0
	for(int i=1;i<=m;i++){
		int u,v,w;//节点,目标节点,权值
		cin>>u>>v>>w;
		a[u][v]=min(a[u][v],w);//赋值,防重边
		a[v][u]=min(a[v][u],w);//(无向图)
		
	}
	for(int k=1;k<=n;k++){//中转点枚举
		for(int i=1;i<=n;i++){//节点枚举
			for(int j=1;j<=n;j++){//目标节点枚举
				a[i][j]=min(a[i][j],a[i][k]+a[k][j]);//最短路更新
			}
		}
	}
	for(int i=1;i<=n;i++){//输出
		for(int j=1;j<=n;j++){
			cout<<a[i][j]<<" ";
		}
		cout<<'\n';
	}
	return 0;
}

二.单源最短路：Dijkstra

简介

        不能处理存在负边权的情况。

        时间复杂度：优化前O() ，优化后O(mlogm)

模板（堆优化）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;//定义常量,根据题目的数据范围改变
struct node{ int v,w; };//目标节点与边权
vector <node> g[N];//存图
int n,m,s,dis[N],vis[N];//节点数,边数,起点,节点到起点的距离,标记
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;//堆优化：距离,目标节点
void Dijkstra(int x){//起点
	memset(dis,0x3f,sizeof(dis));//初始化
	dis[x]=0;//到自身的最短路为0
	q.push({0,s});//入队
	while(q.size()){
		auto t=q.top();q.pop();
		int u=t.second;
		if(vis[u])continue;//如果已经出队就跳过
		vis[u]=1;//标记已入队
		for(int i=0;i<g[u].size();i++){
			int v=g[u][i].v;
			int w=g[u][i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;//更新最短路
				q.push({dis[v],v});
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);//优化
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back((node){v,w});//建图
		//g[v].push_back((node){u,w});无向图
	}
	Dijkstra(s);
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
}

三.Bellman-Ford算法

简介

        能够处理存在负边权的情况，可以用于判断负环。

        时间复杂度：O(nm)

模板（判负环）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;//定义常量,根据题目的数据范围改变
int n,m,s,u[N],v[N],w[N],dis[N];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);//优化
	cin>>n>>m>>s;
	int cnt=0;//判负环：下标
	for(int i=1;i<=m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		cnt++,u[cnt]=a,v[cnt]=b,w[cnt]=c;
		if(c>=0) cnt++,u[cnt]=b,v[cnt]=a,w[cnt]=c;//无向图，为了防止任意两节点均构成负环的误判

	}
	memset(dis,0x3f,sizeof(dis));//初始化
	dis[s]=0;
	bool flag;
	for(int i=1;i<=n;i++){//松弛(正常n-1次，循环n次是为了判断负环)
		flag=false;
		for(int j=1;j<=cnt;j++){//枚举每一条边(如果不判负环就j<=m)
			if(dis[v[j]]>dis[u[j]]+w[j]){//如果是节点s能到达的负环就加上&&dis[u[j]]<1e9的条件
				dis[v[j]]=dis[u[j]]+w[j];//更新最短路
				flag=true;//标记有数据更新
			}
		}
		if(!flag)break;//更新完成,终止
	}
	cout<<(flag?"YES":"NO");//如果第n次仍有数据更新就说明有负环
	return 0;
}

四.SPFA算法

简介

        SPFA是队列优化的Bellman-Ford算法，减少了不必要的冗余计算。

        时间复杂度：O(KE)，E是边数；K是常数，平均值为2

注意

        部分测试点会卡SPFA ！！！

模板（判负环）

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;//定义常量,根据题目的数据范围改变
struct node{ int v,w; };//目标节点与边权
vector <node> e[N];//存图
int n,m,s,dis[N],vis[N],cnt[N];//判负环：cnt记录次数
queue <int> q;
bool SPFA(int x){
	memset(dis,0x3f,sizeof(dis));//初始化
	dis[x]=0;
	vis[x]=1;
	cnt[x]=1;
	q.push(x);
	while(!q.empty()){
		int cur =q.front();q.pop();
		vis[cur]=0;
		for(int i=0;i<e[cur].size();i++){
			int v=e[cur][i].v;
			int w=e[cur][i].w;
			if(dis[v]>dis[cur]+w){
				dis[v]=dis[cur]+w;//更新最短路
				if(!vis[v]){//如果未标记
					q.push(v);
					vis[v]=1;
					cnt[v]++;
					if(cnt[v]>=n)return true;//如果次数大于等于n,有负环
				}
			}
		}
	}
	return false;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);//优化
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		e[a].push_back((node){b,c});
		if(c>=0) e[b].push_back((node){a,c});//无向图，为了防止任意两节点均构成负环的误判
	}
	cout<<(SPFA(s)?"YES":"NO");
	return 0;
}

感谢观看！！！