图论：最短路问题_图上最短路 稀疏

前言：这两天重新回顾了一下图论中的最短路的一些算法，这里做个笔记总结。

目录

使用场景汇总：

单源最短路：

多源最短路：

思路以及算法模板：

1、朴素dikjstra算法

2、堆优化版dikjstra算法

3、bellman_ford算法

4、spfa算法

5、floyd算法

---

使用场景汇总：

单源最短路：

题目模板，给定n个点m条边，求1到n的距离 

边权均为正数的情况：

使用条件：1、当n的数量与m²的数量近似，应使用邻接矩阵的形式储存边权（朴素Dijlstra算法）

                  2、当n的数量与m的数量近似，应使用邻接表的形式储存 边权 （堆优化Dikjstra算法）

边权存在负数的情况：

使用条件：1、存在负权回路，问法通常为给定k条边情况 （bellman-ford算法）

                   2、不存在负权回路，但是边权值存在负数（spfa算法）

备注：1、负权回路即存在至少一个回路，转一圈之后1到当前点的距离变为了负数，那么就可以无限转圈，使得第一个点到当前点的距离无限减小，所以通常题目会给定只能走k次，这个时候就要是用到bellman_ford算法

           2、spfa算法的时间复杂度度最低为O(nm)，所以出题人如果比较坏，很可能会卡住，但是大多数情况不会去卡这个问题，spfa算法通常也能解决dikjstra算法能解决的问题

多源最短路：

使用条件：1、问多个点，而不仅仅是1点到n点的距离（floyd算法）

思路以及算法模板：

1、朴素Dijkstra算法

2、堆优化版dikjstra算法

3、bellman_ford算法

4、spfa算法

5、floyd算法

1、朴素dikjstra算法

题目模板：给定n个点，m条边，存在重边与自环，边权均为正值，输出1到n的距离，如果不能到达则输出-1（这里写稠密图的情况，即用一个二维数组g[a][b]储存a到b的距离）

  

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=510,M=10010;
 
int g[N][N];//储存每个点到另一个点的距离
int dist[N];//储存每个点到1点的距离
int n,m;
bool st[N];//判段当前点是否走过
 
void dikjstra(){
	memset(dist,0x3f,sizeof dist);//将每个点到1点的距离初始化为0x3f3f3f3f;
	dist[1]=0;//1到自身的距离为0;
	for(int i=0;i<n-1;i++){
		int t=-1;
		for(int j=1;j<=n;j++){
			if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j;
		}
		st[t]=true;
		//找到最近的点，用这个点去更新通过这条路到其他点的距离
		for(int j=1;j<=n;j++){
			//如果原来保存的距离大于原点到t的距离，加上t到j的距离，更新
			dist[j]=min(dist[j],dist[t]+g[t][j]);
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	memset(g,0x3f,sizeof g);//将每个点到另一个点的距离初始化为0x3f3f3f3f
	while(m--){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		g[a][b]=min(g[a][b],c);//这里因为存在重边，所以保存一个最小的
	}
	dikjstra();
	if(dist[n]>0x3f3f3f3f/2) puts("-1");
	else printf("%d",dist[n]);
	return 0;
}

  然后我们就会发现，每次都要找距离最近的点是不是太麻烦了呢，所以这里就可以用priority_queue，用堆去优化，在存入的时候就能找到最近的点

2、堆优化版dikjstra算法

注意要用priority_queue<PII,vector<PII>,greater<PII>> 来初始化，因为堆默认为大根堆，最大的存在上面，而通过这个方式就可以改成小根堆，按元素从小到大储存

题目模板与上面的朴素算法一样，但是这里用稀疏图即用领接表演示

#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e6+10;
typedef pair<int,int> PII;
int h[N],w[N],e[N],ne[N],idx;//头结点，当前点指向的下一个点，当前点指向的下一个点的地址，idx用来记录地址
bool st[N];//判段当前点有没有走过
int dist[N];//储存当前点到1点的距离
int n,m;
void add(int a,int b,int c){
	//用数组模拟链表的add
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
 
void dikjstra(){
	memset(dist,0x3f,sizeof dist);
	dist[1]=0;
	priority_queue<PII,vector<PII>,greater<PII>> heap;
	heap.push({0,1});//先将1点到自身的距离加入进去
	while(heap.size()){
		auto t=heap.top();//取出第一个元素
		heap.pop();
		int distance=t.first,var=t.second;
		//如果这个点没走过，用这个点更新这个点到他连接的点的距离
		if(!st[var]){
			st[var]=true;//将这个点更新为走过
			for(int i=h[var];i!=-1;i=ne[i]){
				int j=e[i];//获得这个点链接的所有点
				if(dist[j]>dist[var]+w[i]){
					dist[j]=dist[var]+w[i];
					heap.push({dist[j],j});
				}
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	memset(h,-1,sizeof h);//将每个的头结点设为-1
	while(m--){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
	}
	dikjstra();
	if(dist[n]>0x3f3f3f3f/2) puts("-1");
	else printf("%d",dist[n]);
	return 0;
}

3、bellman_ford算法

bellman_ford算法是一个很慢的算法，我学到的使用情况只有存在负权回路才要用，通常题目会给定最多走k条边

题目模板：给定n个点，m条边，边权可能为负数，可能存在负权回路，求给定k条边的情况下1到n的最小距离，如果不能则，输出impossible。

后面都用邻接表的形式举例子

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+10;
 
int e[N],w[N],ne[N],h[N],idx;
bool st[N];
int dist[N],backup[N];//这里要储存上一次的dist，因为不能让当前的点将当前的距离更新了，否则判段k条边
int n,m,k;
 
struct Edge{
	int a,b,w;
}edges[N];
 
void bellman_ford(){
	memset(dist,0x3f,sizeof dist);
	dist[1]=0;//初始化,将1到本身的距离为0
	for(int i=0;i<k;i++){//循环k次
		memcpy(backup,dist,sizeof dist);//备份
		for(int j=0;j<m;j++){
			auto t=edges[j];
			dist[t.b]=min(dist[t.b],backup[t.a]+t.w);
			//用上一次备份的更新a到b距离
		}
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=0;i<m;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		edges[i]={a,b,c};
	}
	bellman_ford();
	if(dist[n]>0x3f3f3f3f/2) puts("impossible");
	else printf("%d",dist[n]);
	return 0; 
}

backup再重新记一下，因为比如1到2的距离是1,2到3的距离是1,1到3的距离是2，按照我们通常的写法，这里会用1到2的距离更新1到3的距离，但是用了两条边，我们假设1条边的情况下这个写法就是错误的了，所以要用backup来备份，这样就会用负无穷来更新1到3的距离。

4、spfa算法

spfa算法可以使用于边权值存在负数的情况，但是如果存在负权回路，则不能用spfa算法

很使用，写起来很简单，所以这个是重点，通常不会卡spfa和dikjstra算法之间时间复杂度差距

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int N=1e5+10;
 
int h[N],e[N],w[N],ne[N],idx;
bool st[N];//这里的st判段的是是否储存在队列中
int dist[N];
int 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(){
	memset(dist,0x3f,sizeof dist);//初始化每个点到1的距离为0x3f3f3f3f
	dist[1]=0;
	queue<int> q;
	q.push(1);
	st[1]=0;//初始化，把1加入队列
	while(q.size()){
		int t=q.front();
		q.pop();
		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];
				if(!st[j]){//将要更新的点加入队列
					st[j]=true;
					q.push(j);
				}
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	memset(h,-1,sizeof h);//初始化头结点为-1
	while(m--){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
	}
	spfa();
	if(dist[n]>0x3f3f3f3f/2 ) puts("impossible");
	else printf("%d",dist[n]);
	return 0;
}

注意，这里的st与前面的st的含义不一样，这里的st指的是是否在队列中

5、floyd算法

floyd算法通常是多个点到一个点的距离，时间复杂度为n的三次放，实现原理为动态规划，用i到w的距离和w到j的距离更新i到j的距离，代码较简单，但是注意循环次序为wij

题目模板：给定n个点m条边，边权可能为负数，不存在负权回路，给定k个查询，每个查询包含两个数a和b，求x到y的最短距离，如果不能到则输出impossible

第一行输入n,m,q

后m行输入a,b,w

后q行输入查询a,b

#include<iostream>
#include<algorithm>
#include<cstring>
 
using namespace std;
const int N=210,INF=1e9+10;
int d[N][N];//代表两个点的距离
int n,m,q;
 
void floyd(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}
}
 
int main(){
	scanf("%d%d%d",&n,&m,&q);
	//初始化，让每个点到自身的距离为0，到其他点的距离为0x3f3f3f3f
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j) d[i][j]=0;
			else d[i][j]=INF;
		}
	}
	while(m--){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		d[a][b]=min(d[a][b],c);
	}
	floyd();
	while(q--){
		int a,b;
		scanf("%d%d",&a,&b);
		if(d[a][b]>0x3f3f3f3f/2) puts("impossible");
		else printf("%d\n",d[a][b]); 
	}
	return 0;
}

后文：

1、函数都是用的void返回，因为如果边权存在负数的情况，设的走不到返回-1，如过dist[n]=-1，就会出现问题，但是正数不存在这个问题

2、为什么用if(d[a][b]>0x3f3f3f3f/2)，因为如果边权纯在负数，会用这个距离去更新其他的点，导致他的距离不为0x3f3f3f3f，可能是0x3f3f3f3f-2或者-3这种，所以每次都用他大于一个数做比较，亲测都能过