最短路讲解【算法竞赛 - 10.8】

最短路算法有很多种，都用于解决图论中两点之间最短路径问题。

板子题传送门->（天立OJ）

最短路问题无非就三种：

是否需要计算边权
是否存在负环（图中存在一个环，环上所有边权和为负数）
单源最短路 / 多源最短路

针对这些类型的最短路问题，就诞生了各类的最短路算法。

一、 Floyd 算法（全称Floyd-Warshall算法）

特点：容易编码，思路简单，能处理多源最短路问题和找出图中的负环

能一次性求得所有节点之间的最短距离，其他的最短路算法做不到。 ——《算法竞赛·下册》

算法效率： $O(n^3)$ ，效率特别慢，能处理图中点数为300以内的数据
算法空间：由于使用邻接矩阵记录边和记录答案，所以需要n*n的空间，占用很大空间，但在400范围内绝对足够的。
算法思路：
- 先初始化所有点之间距离为INF
- 最外层循环遍历所有中转点k
- 第二层和第三层循环遍历所有起点和终点i和j
- 更新起点和终点i和j的最短距离

一阵操作后，就等于尝试了所有点之间的所有走法，自然能得出最短路径。最后邻接矩阵中就得到了所有点之间的最短距离。

5.注意：

可能存在重边：只存入更短的一条边
判断负环：如果任意两点之间出现了距离dis[i][j] < 0那么就存在负环
注意三层循环的顺序，最外层是中转点，里面两层是起点和终点

AC代码

CPP

#include<cstdio>
#include<algorithm>

using namespace std;

const int maxn = 1005, INF = 1e9 + 5;

int n, m, s, t, dis[maxn][maxn];
void Init() {
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			if (i != j) {
				dis[i][j] = INF;
			}
		}
	}
}

void Input() {
	scanf("%d %d %d %d", &n, &m, &s, &t);
	Init();															//注意Init()的位置，否则会影响正常边的存入
	for (int i = 1, u, v, w; i <= m; ++i) {
		scanf("%d %d %d", &u, &v, &w);
		dis[u][v] = dis[v][u] = min(dis[u][v], w);					//解决重边问题，只记录最小的一个边
	}
}

void Floyd() {
	for (int k = 1; k <= n; ++k) {									//遍历中转点
		for (int i = 1; i <= n; ++i) {								//遍历起点
			for (int j = 1; j <= n; ++j) {							//遍历终点
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);	//更新起点到终点的最短路径
			}
		}
	}
}

void Print() {
	printf("%d", dis[s][t]);
}

int main() {
	Input();
	Floyd();
	Print();
	return 0;
}

最短路讲解【算法竞赛 - 10.8】

文章操作

一、 Floyd 算法（全称Floyd-Warshall算法）

相关推荐

评论

最短路讲解【算法竞赛 - 10.8】