成都百度网站制作,妙趣网 通辽网站建设,交易平台网站模板,公司网站开发说明介绍目录 引言一、最短路问题二、朴素Dijkstra算法三、堆优化版的Dijkstra算法四、Bellman-Ford算法五、SPFA算法六、Floyd算法 引言
这个最短路问题可以说是图论当中的基础问题#xff0c;不管你干什么只要涉及图论中的问题的话#xff0c;最短路问题都是你不可避免的#xff… 目录 引言一、最短路问题二、朴素Dijkstra算法三、堆优化版的Dijkstra算法四、Bellman-Ford算法五、SPFA算法六、Floyd算法 引言
这个最短路问题可以说是图论当中的基础问题不管你干什么只要涉及图论中的问题的话最短路问题都是你不可避免的不论是在算法竞赛、考研、面试都是非常重要的本文介绍了Dijkstra算法、堆优化版的Dijkstra算法、Bellman-Ford算法、SPFA算法、Floyd算法的思想以及例题并且介绍了在什么情况下用什么算法话不多说直接开干。
一、最短路问题
这张图涵盖了所有的最短路问题接下来就一一介绍啦 单源一个起点多源多个起点
二、朴素Dijkstra算法
思想先找到一个点到起点的最短距离然后再看能不能通过这个点更新其它点到起点的距离然后再找到另一个点到起点的最短距离再次更新直至更新至终点
题目描述
给定一个 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 3
1 2 2
2 3 1
1 3 4
输出样例
3示例代码
#include cstdio
#include cstring
#include iostreamusing namespace std;const int N 510;int n, m;
int g[N][N]; //稠密图采用邻接矩阵存储方式
int dist[N]; //代表起点到i号点的最短距离
bool st[N]; //当前已确定最短距离的点int dijkstra()
{memset(dist, 0x3f, sizeof dist);dist[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;}for(int j 1; j n; j) dist[j] min(dist[j], dist[t] g[t][j]);st[t] true;}if(dist[n] 0x3f3f3f3f) return -1;return dist[n];
}int main()
{scanf(%d%d, n, m);memset(g, 0x3f, sizeof g);while(m--){int a, b, c;scanf(%d%d%d, a, b, c);g[a][b] min(g[a][b], c);}printf(%d\n, dijkstra());return 0;
}三、堆优化版的Dijkstra算法
这个堆优化版本的就是把找最短距离的边换成堆来优化就行了把边全部加到堆中然后每次取堆顶就行了
题目描述
给定一个 n 个点 m 条边的有向图图中可能存在重边和自环所有边权均为非负值。请你求出 1 号点到 n 号点的最短距离如果无法从 1 号点走到 n 号点则输出 −1。输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边边长为 z。输出格式
输出一个整数表示 1 号点到 n 号点的最短距离。
如果路径不存在则输出 −1。数据范围
1≤n,m≤1.5×105,图中涉及边长均不小于 0且不超过 10000。
数据保证如果最短路存在则最短路的长度不超过 109。输入样例
3 3
1 2 2
2 3 1
1 3 4
输出样例
3示例代码
#include cstdio
#include cstring
#include iostream
#include queueusing namespace std;typedef pairint,int PII; //存的是权重, 结点编号const int N 2e510;int n, m;
int h[N], e[N], w[N], ne[N], idx; //因为是稀疏图用邻接表
int dist[N];
bool st[N];void add(int a, int b, int c)
{e[idx] b, w[idx] c; ne[idx] h[a], h[a] idx;
}int dijkstra()
{memset(dist, 0x3f, sizeof dist);dist[1] 0;priority_queuePII, vectorPII, greaterPII heap; //初始化小根堆heap.push({0,1});while(heap.size()){auto t heap.top(); heap.pop();int ver t.second, distance t.first;if(st[ver]) continue;st[ver] true;for(int i h[ver]; i ! -1; i ne[i]){int j e[i];if(dist[j] distance w[i]){dist[j] distance w[i];heap.push({dist[j], j});}}}if(dist[n] 0x3f3f3f3f) return -1;return dist[n];
}int main()
{memset(h, -1, sizeof h);scanf(%d%d, n, m);while(m--){int a, b, c;scanf(%d%d%d, a, b, c);add(a, b, c);}printf(%d\n,dijkstra());return 0;
}四、Bellman-Ford算法
思想通过遍历k次每次都遍历所有边更新所有边
题目描述
给定一个 n 个点 m 条边的有向图图中可能存在重边和自环 边权可能为负数。请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离如果无法从 1 号点走到 n 号点输出 impossible。
注意图中可能 存在负权回路 。输入格式
第一行包含三个整数 n,m,k。
接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边边长为 z。点的编号为 1∼n。输出格式
输出一个整数表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。
如果不存在满足条件的路径则输出 impossible。数据范围
1≤n,k≤500,1≤m≤10000,1≤x,y≤n
任意边长的绝对值不超过 10000。输入样例
3 3 1
1 2 1
2 3 1
1 3 3输出样例
3示例代码
#include cstdio
#include cstring
#include iostreamusing namespace std;const int N 510, M 10010;int n, m, k;
int dist[N], backup[N];struct Edge
{int a, b, c;
}edges[M];void bellman_ford()
{memset(dist, 0x3f, sizeof dist);dist[1] 0;for(int i 0; i k; i){memcpy(backup, dist, sizeof dist); //防止串行赋值导致超出k次for(int j 0; j m; j){auto e edges[j];dist[e.b] min(dist[e.b], backup[e.a] e.c); //每次只会通过一个顶点更新边}}
}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); //因为更新边要是INF -1 也是INF, 但不是0x3f3f3f3f了else printf(%d\n, dist[n]);return 0;
}五、SPFA算法
思想把第一个点加入队列中然后用这个点更新与之相连的点然后把更新的点加入队列中把之前的点取出队列
题目描述
给定一个 n 个点 m 条边的有向图图中可能存在重边和自环 边权可能为负数。
请你求出 1 号点到 n 号点的最短距离如果无法从 1 号点走到 n 号点则输出 impossible。
数据保证不存在负权回路。输入格式
第一行包含整数 n 和 m。
接下来 m 行每行包含三个整数 x,y,z表示存在一条从点 x 到点 y 的有向边边长为 z。输出格式
输出一个整数表示 1 号点到 n 号点的最短距离。
如果路径不存在则输出 impossible。数据范围
1≤n,m≤105,图中涉及边长绝对值均不超过 10000。输入样例
3 3
1 2 5
2 3 -3
1 3 4
输出样例
2示例代码
#include cstdio
#include cstring
#include iostreamusing namespace std;const int N 1e510;int n, m;
int h[N], e[N], w[N], ne[N], idx;
int dist[N], q[N];
bool st[N];void add(int a, int b, int c)
{e[idx] b, w[idx] c, ne[idx] h[a], h[a] idx;
}int spfa()
{memset(dist, 0x3f, sizeof dist);dist[1] 0;st[1] true;int hh 0, tt -1;q[tt] 1;while(hh tt){auto t q[hh];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]){q[tt] j;st[j] true;}}}}return dist[n];
}int main()
{memset(h, -1, sizeof h);scanf(%d%d, n, m);while(m--){int a, b, c;scanf(%d%d%d, a, b, c);add(a, b, c);}int t spfa();if(t 0x3f3f3f3f) puts(impossible);else printf(%d\n, t);return 0;
}六、Floyd算法
这个算法基于动态规划dist[i][j] 刚开始跟g[i][b]一样之后就变成了i - j 的最短距离
//dist(k, i, j) 代表从i - j 能经过 1 - k 个点的最短距离
dist(k, i, j) dist(k-1, i, k) dist(k-1, k, j)题目描述
给定一个 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≤n21≤m≤20000,图中涉及边长绝对值均不超过 10000。输入样例
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3输出样例
impossible
1示例代码
#include cstdio
#include cstring
#include iostreamusing namespace std;const int N 210, INF 1e9;int n, m, Q;
int dist[N][N];void floyd()
{for(int k 1; k n; k)for(int i 1; i n; i)for(int j 1; j n; j)dist[i][j] min(dist[i][j], dist[i][k] dist[k][j]);
}int main()
{scanf(%d%d%d, n, m, Q);for(int i 1; i n; i){for(int j 1; j n; j){if(i j) dist[i][j] 0;else dist[i][j] INF;}}while(m--){int a, b, c;scanf(%d%d%d, a, b, c);dist[a][b] min(dist[a][b], c);}floyd();while(Q--){int a, b;scanf(%d%d, a, b);if(dist[a][b] INF / 2) puts(impossible);else printf(%d\n, dist[a][b]);}return 0;
}
