最短路算法总结

本文主要是介绍最短路算法总结，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

最短路算法总结

一、目录

1.Floyd（n^3) n：点数

2.dijikstra( n^2 -> mlogn) n：点数 m:边数（不理解复杂度）

3.bellman-ford(nm) n: 点数 m:边数

4.spfa(Km) K:约为2的常数 m:边数

5.Johnson (nmlogm) （不理解复杂度）

二、实现的代码

1.floyd 全源最短路（可以解决负权边，但不能解决负权回路）

代码的核心：从第i点到第j点的过程中，寻找是否有第k点（k ！= i && k ！= j）作为中转点，使得i点和j点之间的最短路可以更新，从而完成代码。

要注意：k要放在最外层循环（本质与动规状态转移有关）否则对于一些神奇的数据点，会出错！！！

#include<bits/stdc++.h>
using namespace std;
#define N 200//基本为最大数据范围

int f[N][N];//两个点之间的最短距离 
int main(){
	int n, m;//n为点的数目，m为边的数目
	scanf("%d%d", &n, &m);
	memset(f, 0x3f, sizeof(f));//初始化为无穷大
	for(int i = 1; i <= n; ++ i)
		f[i][i] = 0;//自己到自己的距离初始化为0
	for(int j = 1; j <= m; ++ m){
		scanf("%d%d%d", &x, &y, &z);
		if(z < f[x][y]) f[x][y] = f[y][x] = z;
	}
	for(int k = 1; k <= n; ++ k)//k必须在最外层循环，作为动态转移的状态
		for(int i = 1; i <= n; ++ i)
			for(int j = 1; j <= n; ++ j)
				if(i != k && i != j && k != j && f[x][k] + f[k][y] < f[x][y]) f[x][y] = f[y][x] = f[x][k] + f[k][y];
	f[a][b]即为a,b两点之间的最短距离
	return 0;
}

2.dijikstra 单源最短路（不能解决负权边）

代码的核心：松弛操作若能实现，将点加入到优先队列中，每次取出距离起点最短距离的点进行拓展，并且保证每个点只进行一次遍历它所有相邻的点。

此处代码直接用堆优化，因为不优化的dijikstra意义不大（时间复杂度高）

注意：压入队列时，要压边权的相反数！（默认大根堆）

#include<bits/stdc++.h>
using namespace std;
const int N = 1050;//基本为最大数据范围 
int dis[N];
bool vis[N];
vector<pair <int , int> >vec[N];
priority_queue<pair <int , int> >que;//大根堆 
void dijikstra(int x){
	que.push(make_pair(0, x));
	dis[x] = 0;
	while(!que.empty()){
		int u = que.top().second;
		que.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		int len = vec[u].size();
		for(int i = 0; i < len; ++ i){
			int v = vec[u][i].first;
			int w = vec[u][i].second;
			if(dis[u] + w < dis[v]){
				dis[v] = dis[u] + w;
				que.push(make_pair(-dis[v], v));//压
			}
		}
	}
	return ;
}
int main(){
	int x, y, v;
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++ i){
		scanf("%d%d%d", &x, &y, &v);
		vec[x].push_back(make_pair(y, v));
		vec[y].push_back(make_pair(x, v));
	}
	int center;
	scanf("%d", &center);
	memset(dis, 63, sizeof(dis));
	dijikstra(center);//求出以center为起点的各点的最短路，存储在dis数组中 
	printf("%d", dis[目标点]);
	return 0;
}

3.bellman-ford 单源最短路（能解决负权边,不能解决负环，但可以判断负环）

代码核心：跑n次循环，每次跑m条边的首尾点之间的距离，如果能更新就及时更新。

#include<bits/stdc++.h>
using namespace std;
#define N 3050

struct Edge{
	int u, v;
	int w;
}edge[N];//结构体数组用来存边 
int dis[N];
int main(){
	int U, V;//起点和终点 
	scanf("%d%d", &U, &V);
	memset(dis, 63, sizeof(dis));
	dis[U] = 0;//初始化 
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++ i)
		scanf("%d%d%d", &edge[i].u, &edge[i].v, edge[i].w);
	for(int i = 1; i <= n; ++ i)
		for(int j = 1; j <= m; ++ j){
			if(dis[edge[j].u] + edge[j].w < dis[edge[j].v])
				dis[edge[j].v] = dis[edge[j].u] + edge[j].w;
			if(dis[edge[j].v] + edge[j].w < dis[edge[j].u])
				dis[edge[j].u] = dis[edge[j].v] + edge[j].w;
		}
	for(int j = 1; j <= m; ++ j)
		if(dis[edge[j].u] + edge[j].w < dis[edge[j].v] || dis[edge[j].v] + edge[j].w < dis[edge[j].u])
			printf("存在负环！！！")
	printf("%d", dis[V]);
	return 0;
}

4.spfa求单源最短路（能解决负权边，不能解决负环，可判断负环）

代码核心：用队列优化后的bellman-Ford算法，省去了冗余的循环，大大极高运行效率。

#include<bits/stdc++.h>
using namespace std;
const int N = 200010;

int n, m;
vector<pair<int, int> >vec[N];
queue<pair<int, int> >que;

int dis[N], d[N];//d[N]为走最短路到达某点所需步数 
bool vis[N];
int spfa(int s)
{
	memset(dis, 63, sizeof(dis));
	dis[s] = 0;
	vis[s] = 1;
	que.push(make_pair(0, s));
	while(!que.empty())
	{
		int u = que.front().second;
		vis[u] = 0;
		que.pop();
		for(int i = 0; i < vec[u].size(); ++i){
			int v = vec[u][i].first;
			int w = vec[u][i].second;
			if(dis[u] + w < dis[v]){
				dis[v] = dis[u] + w;
				d[v] = d[u] + 1;
				if(d[v] >= n) return 1;//若无负环，走最短路到达某点最多用n-1条边 
				if(!vis[v]){
					vis[v] = 1;
					que.push(make_pair(dis[v], v));
				}	
			}
		}
	}
	return 0;
}
int main()
{
	scanf("%d%d", &n, &m);	
	int x, y, z;
	for(int i = 1; i <= m; ++i){
		scanf("%d%d%d", &x, &y, &z);
		vec[x].push_back(make_pair(y, z));
		vec[y].push_back(make_pair(x, z));
	}
	int U, V;//U:起点 V：终点 
	scanf("%d%d", &U, &V);
	int judge = spfa(U);
	if(judge == 1) puts("存在负环！！！")
	else	printf("%d", dis[V]);
	return 0;
}

5.johnson全源最短路（能解决负权边，不能解决负环，可以判断负环）

代码关键：bellman-ford与dijikstra的配合使用，大数据范围下优于spfa算法跑n次。

转载【洛谷日报#242】Johnson 全源最短路径算法学习笔记
链接：https://zhuanlan.zhihu.com/p/99802850

练习题：P5905 【模板】Johnson 全源最短路
链接：https://www.luogu.com.cn/problem/P5905

建议先看笔记，后做题，下面是本题题解

#include<bits/stdc++.h>
using namespace std;
#define N 3005

int h[N], vis[N];
long long dis[N];
struct Edge{
	int u, v;
	int w;
}edge[N * 2];//结构体数组用来存边
vector<pair <int , int> >vec[N];
priority_queue<pair <long long , int> >que;//大根堆 
void dijikstra(int x){
	memset(vis, 0, sizeof(vis));
	que.push(make_pair(0, x));
	dis[x] = 0;
	while(!que.empty()){
		int u = que.top().second;
		que.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		int len = vec[u].size();
		for(int i = 0; i < len; ++ i){
			int v = vec[u][i].first;
			int w = vec[u][i].second;
			if(dis[u] + w < dis[v]){
				dis[v] = dis[u] + w;
				que.push(make_pair(-dis[v], v));
			}
		}
	}
	return ;
} 
int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	int x, y, z;
	for(int i = 1; i <= m; ++ i){
		scanf("%d%d%d", &x, &y, &z);
		edge[i].u = x;
		edge[i].v = y;
		edge[i].w = z;
	}
	for(int i = 0; i <= n; ++ i)
		for(int j = 1; j <= m; ++ j){
			if(h[edge[j].u] + edge[j].w < h[edge[j].v])
				h[edge[j].v] = h[edge[j].u] + edge[j].w;			
		}
	for(int j = 1; j <= m; ++ j)
		if(h[edge[j].u] + edge[j].w < h[edge[j].v]){
			puts("-1");
			return 0;
		}
	for(int i = 1; i <= m; ++ i)
		vec[edge[i].u].push_back(make_pair(edge[i].v, edge[i].w + h[edge[i].u] - h[edge[i].v]));
	for(int i = 1; i <= n; ++ i)
		dis[i] = 1e9;
	for(int i = 1; i <= n; ++ i){
		dijikstra(i);
		long long tot = 0;
		for(int j = 1; j <= n; ++ j){
			if(dis[j] == 1e9) tot += j * 1e9;
			else tot += j * (dis[j] + h[j] - h[i]);
			dis[j] = 1e9;
		}
		printf("%lld\n", tot);
	}
	return 0;
}

以上就是最短路算法的总结了，想必还是有一些错误的存在，欢迎大家批评指正。整理不易，如果给你带来了一些帮助，希望能点赞转发，谢谢！！！

这篇关于最短路算法总结的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程