行业知识
图论 - 最短路（Dijkstra、Bellman-Ford、SPFA、Floyd）
文章目录
- 前言
- Part 1：朴素Dijkstra算法
- 一、Dijkstra求最短路 I
- 1.问题描述
- 输入格式
- 输出格式
- 数据范围
- 输入样例：
- 输出样例：
- 2.算法
- Part 2：堆优化Dijkstra算法
- 一、Dijkstra求最短路 II
- 1.题目描述
- 输入格式
- 输出格式
- 数据范围
- 输入样例：
- 输出样例：
- 2.算法
- Part 3：Bellman-Ford算法
- 一、有边数限制的最短路
- 1.题目描述
- 输入格式
- 输出格式
- 数据范围
- 输入样例：
- 输出样例：
- 2.算法
- Part 4：SPFA算法
- 一、spfa求最短路
- 1.题目描述
- 输入格式
- 输出格式
- 数据范围
- 输入样例：
- 输出样例：
- 2.算法
- 二、spfa判断负环
- 1.题目描述
- 输入格式
- 输出格式
- 数据范围
- 输入样例：
- 输出样例：
- 2.算法
- Part 5：Floyd算法
- 一、Floyd求最短路
- 1.题目描述
- 输入格式
- 输出格式
- 数据范围
- 输入样例：
- 输出样例：
- 2.���法
前言
单源：在边权正数时，稠密图用朴素Dijkstra，稀疏图用堆优化Dijkstra；存在负权边时，一般用SPFA，但是如果限制在k步内，则用Bellman-Ford。多源：只有Floyd，这个由于时间复杂度太高，在算法比赛中很少遇见。
Part 1：朴素Dijkstra算法
一、Dijkstra求最短路 I
1.问题描述
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。
输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
数据范围
1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000。
输入样例：
3 31 2 22 3 11 3 4
输出样例：
3
2.算法
- 即进行n（n为n的个数）次迭代去确定每个点到起点的最小值，最后输出的终点的即为我们要找的最短路的距离。
- 每次迭代的过程中我们都先找到当前未确定的最短距离的点中距离起点最短的点，且在已找到点集合中加上此点，更新其他未找到点距离起点的最短距离。
- 稠密图用邻接矩阵存储
#include #include #include using namespace std;const int N = 510;int n, m;int g[N][N]; //存图int dist[N]; //存距离起点距离bool st[N]; //看是否已经计算过int dijkstra(){ memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i distance + w[i]) { dist[j] = distance + w[i]; heap.push({ dist[j], j }); } } } if(dist[n] == 0x3f3f3f3f) return -1; else return dist[n];}int main(){ memset(h, -1, sizeof(h)); scanf("%d%d", &n, &m); while (m--) { int x, y, c; scanf("%d%d%d", &x, &y, &c); add(x, y, c); } cout dist[a] + c) { dist[b] = dist[a] + c;//更新距离//如果没在队列中 if(!st[b]) { q[++tt] = b;//入队 st[b] = 1;//打标记 } } } }}int main(){ memset(h, -1, sizeof h);//初始化邻接表 memset(dist, 0x3f, sizeof dist);//初始化距离 int n, m;//保存点的数量和边的数量 cin >> n >> m; //读入每条边和边的端点 for(int i = 0; i > a >> b >> w; add(a, b, w);//加入到邻接表 } spfa(); if(dist[n] == 0x3f3f3f3f )//如果到n点的距离是无穷，则不能到达 cout > n >> m; for (int i = 0; iPart 5：Floyd算法
一、Floyd求最短路
1.题目描述
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。
再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 impossible。
数据保证图中不存在负权回路。
输入格式
第一行包含三个整数 n,m,k。
接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。
接下来 k 行，每行包含两个整数 x,y，表示询问点 x 到点 y 的最短距离。
输出格式
共 k 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible。
数据范围
1≤n≤200,
1≤k≤n2
1≤m≤20000,
图中涉及边长绝对值均不超过 10000。
输入样例：
3 3 21 2 12 3 21 3 12 11 3
输出样例：
impossible1
2.算法
-
动态规划
-
假设节点序号是从1到n。
假设f[0][i][j]是一个n*n的矩阵，第i行第j列代表从i到j的权值，如果i到j有边，那么其值就为ci,j（边ij的权值）。
如果没有边，那么其值就为无穷大。
f[k][i][j]代表（k的取值范围是从1到n），在考虑了从1到k的节点作为中间经过的节点时，从i到j的最短路径的长度。
比如，f[1][i][j]就代表了，在考虑了1节点作为中间经过的节点时，从i到j的最短路径的长度。
分析可知，f[1][i][j]的值无非就是两种情况，而现在需要分析的路径也无非两种情况，i=>j，i=>1=>j：
【1】f[0][i][j]：i=>j这种路径的长度，小于，i=>1=>j这种路径的长度
【2】f[0][i][1]+f[0][1][j]：i=>1=>j这种路径的长度，小于，i=>j这种路径的长度
形式化说明如下：
f[k][i][j]可以从两种情况转移而来：
【1】从f[k−1][i][j]转移而来，表示i到j的最短路径不经过k这个节点
【2】从f[k−1][i][k]+f[k−1][k][j]转移而来，表示i到j的最短路径经过k这个节点
总结就是：f[k][i][j]=min(f[k−1][i][j],f[k−1][i][k]+f[k−1][k][j])
从总结上来看，发现f[k]只可能与f[k−1]有关。
#include #include #include using namespace std;const int N = 210, INF = 1e9;int n, m, Q;int d[N][N];void floyd(){ for (int k = 1; k
-
上一篇：怎么出现服务器检测?
下一篇：景安快云vps怎么重启
