求最短路径的三种算法_最短路径算法

目录

一.单源最短路

1.dijkstra算法及实现

2.spfa算法及实现

（1）spafa负环判断及实现

二.多源最短路

1.floyd算法及实现

一.单源最短路

1.dijkstra算法及实现
求源点到图中其余各顶点的最短路径
dfs效率慢,解决规模小，bfs只能边权为1的图
Dijkstra算法——迪杰斯塔拉算法（非负全图）
 基本思想:
 首先假定源点为u，顶点集合V被划分为两部分：集合 S 和 V-S.
 初始时S中仅含有源点u，其中S中的顶点到源点的最短路径已经确定。
集合S 和V - S中所包含的顶点到源点的最短路径的长度待定，
 称从源点出发只经过S中的点到达V - S中的点的路径为特殊路径，
并用dist[]记录当前每个顶点对应的最短特殊路径长度。
实现从1到n的最短路径
 输入：
3 3
1 2 5
2 3 5
3 1 2
输出：
2

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1001;
const int M = 10001;
int head[N];
int size1;
int n, m;
struct edge {
	int v, w, next;
	edge() {};
	edge(int _v, int _w, int _next) {
		v = _v;
		w = _w;
		next = _next;
	}
}e[M*2];
void init() {
	memset(head, -1, sizeof(head));
	size1 = 0;;
 
}
void insert(int u,int v,int w) {
	e[size1] = edge(v, w, head[u]);
	head[u] = size1++;
}
void insert2(int u, int v, int w) {
	insert(u, v, w);
	insert(v, u, w);
}
int dis[N];
bool vis[N];
void dijkstra(int u)
{
	memset(vis, false, sizeof(vis));
	memset(dis, 0x3f, sizeof(dis));       //0x3f用以表示正无穷
	dis[u] = 0; 
	int mind = 1000000000;
	for (int i = 0; i < n; i++) {
		int minj = -1;
		for (int j = 1; j <= n; j++) {
			if (!vis[j] && dis[j] < mind) {
				minj = j;
				mind = dis[j];
			}
		}
		if (minj == -1)
			return;
		vis[minj] = true;
		for (int j = head[minj];~j ; j = e[j].next) {  ///~j等价于j!=-1;
			int v = e[j].v;
			int w = e[j].w;
			if (!vis[v] && dis[v] > dis[minj] + w)
				dis[v] = dis[minj] + w;
		}
	}
}
int main()
{
	init();
	int u, v, w;
	cin >> n >> m;
	while (m--) {
		cin >> u >> v >> w;
		insert2(u, v, w);
	}
	dijkstra(1);
	cout << dis[n] << endl;
	return 0;
}

2.SPFA算法——Shortest Path Faster Algorithm 
思路：
用数组dis记录每个结点的最短路径估计值，用邻接表或邻接矩阵来存储图G。
我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，
优化时每次取出队首结点u，
并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，
如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。
这样不断从队列中取出结点来进行松弛操作，直至队列空为止
优点：
（可以解决带负权的有向图并且在稀疏图优于dijsktra）
反例：
 1.出题特殊数据使SPFA算法慢，2.有负环不能解决
推荐后续优化的dijkstra算法
实现：

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1001;
const int M = 10001;
int head[N];
int size1;
int n, m;
struct edge {
	int v, w, next;
	edge() {};
	edge(int _v, int _w, int _next) {
		v = _v;
		w = _w;
		next = _next;
	}
}e[M*2];
void init() {
	memset(head, -1, sizeof(head));
	size1 = 0;;
 
}
void insert(int u,int v,int w) {
	e[size1] = edge(v, w, head[u]);
	head[u] = size1++;
}
void insert2(int u, int v, int w) {
	insert(u, v, w);
	insert(v, u, w);
}
int dis[N];
bool vis[N];
void spfa(int u) {
	memset(vis, false, sizeof(vis));
	vis[u] = true;
	memset(dis, 0x3f, sizeof(dis));
	dis[u] = 0;
	queue<int>q;
	q.push(u);
	while (!q.empty()) {
		u = q.front();
		q.pop();
		vis[u] = false;
		for (int j = head[u]; ~j; j = e[j].next) {
			int v = e[j].v;
			int w = e[j].w;
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				if (!vis[v]) {
					q.push(v);
					vis[v] = true;
				}
			}
 
		}
	}
}
int main()
{
	init();
	int u, v, w;
	cin >> n >> m;
	while (m--) {
		cin >> u >> v >> w;
		insert2(u, v, w);
	}
	spfa(1);
	cout << dis[n] << endl;
	return 0;
}

（1）spfa判断负环
在进行spfa用一个数组cnt标记每个顶点的入队次数，如果一个顶点的入队次数大于顶点总数
则表示该图含有负环

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1001;
const int M = 10001;
int head[N];
int size1;
int n, m;
struct edge {
	int v, w, next;
	edge() {};
	edge(int _v, int _w, int _next) {
		v = _v;
		w = _w;
		next = _next;
	}
}e[M*2];
void init() {
	memset(head, -1, sizeof(head));
	size1 = 0;;
 
}
void insert(int u,int v,int w) {
	e[size1] = edge(v, w, head[u]);
	head[u] = size1++;
}
void insert2(int u, int v, int w) {
	insert(u, v, w);
	insert(v, u, w);
}
int dis[N], in[N];
bool vis[N];
bool spfa(int u) {
	memset(vis, false, sizeof(vis));
	vis[u] = true;
	memset(dis, 0x3f, sizeof(dis));
	dis[u] = 0;
	memset(in, 0, sizeof(in));
	in[u] = u;
	queue<int>q;
	q.push(u);
	while (!q.empty()) {
		u = q.front();
		q.pop();
		vis[u] = false;
		for (int j = head[u]; ~j; j = e[j].next) {
			int v = e[j].v;
			int w = e[j].w;
			if (dis[v] > dis[u] + w)
				dis[v] = dis[u] + w;
			if (!vis[v]) {
				q.push(v);
				vis[v] = false;
				++in[v];
				if (in[v] > n)
					return true;
			}
		}
	}
	return false;
}
int main()
{
	init();
	int u, v, w;
	cin >> n >> m;
	while (m--) {
		cin >> u >> v >> w;
		insert2(u, v, w);
	}
	if (spfa(1))
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	return 0;
}

二.多源最短路
1.floyd算法——（Floyd-Warshall algorithm），中文亦称弗洛伊德算法
利用动态规划的思想解决带权图中任意两个点之间最短路径算法
优势：代码简短，高效，可以解决带负权

反例：不能解决带负环
思路：
dp[0][i][j]=图
dp[k][i][j]=从i到j可能经过1...k最短路径，
min(dp[k][i][j],dp[k-1][i][k]+dp[k-1][k][j])
优化为二维：
min(dp[i][j],dp[i][k]+dp[k][j])
实现：
 

#include<iostream>
#include<cstring>
using namespace std;
const int N = 101;
int g[N][N];
void floyd(int n) {
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				g[i][j] = min(g[i][j], g[i][k] + g[j][k]);
			}
		}
	}
}
int main()
{
	memset(g, 0x3f, sizeof(g));
	for (int i = 0; i < N; i++) {
		g[i][i] = 0;
	}
	int n, m;
	int u, v, w;
	cin >> n >> m;
	while (m--) {
		cin >> u >> v >> w;
		g[u][v] = g[v][u] = w;
	}
	floyd(n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << g[i][j] << ' ';
		}
		cout << endl;
	}
	return 0;
}