当前位置:   article > 正文

图论(二):图的四种最短路径算法

最短路径

本文总结了图的几种最短路径算法的实现:深度或广度优先搜索算法,弗洛伊德算法,迪杰斯特拉算法,Bellman-Ford算法


1),深度或广度优先搜索算法(解决单源最短路径)
从起始结点开始访问所有的深度遍历路径或广度优先路径,则到达终点结点的路径有多条,取其中路径权值最短的一条则为最短路径。

下面是核心代码:

  1. void dfs(int cur, int dst){
  2. /***operation***/
  3. /***operation***/
  4. if(minPath < dst) return;//当前走过路径大于之前最短路径,没必要再走下去
  5. if(cur == n){//临界条件
  6. if(minPath > dst) minPath = dst;
  7. return;
  8. }
  9. else{
  10. int i;
  11. for(i = 1; i <= n; i++){
  12. if(edge[cur][i] != inf && edge[cur][i] != 0 && mark[i] == 0){
  13. mark[i] = 1;
  14. dfs(i, dst+edge[cur][i]);
  15. mark[i] = 0; //需要在深度遍历返回时将访问标志置0
  16. }
  17. }
  18. return;
  19. }
  20. }
例1:下面是城市的地图,注意是单向图,求城市1到城市5的最短距离。(引用的是上次总结的图论(一)中1)的例2)

  1. /***先输入n个结点,m条边,之后输入有向图的m条边,边的前两元素表示起始结点,第三个值表权值,输出1号城市到n号城市的最短距离***/
  2. /***算法的思路是访问所有的深度遍历路径,需要在深度遍历返回时将访问标志置0***/
  3. #include <iostream>
  4. #include <iomanip>
  5. #define nmax 110
  6. #define inf 999999999
  7. using namespace std;
  8. int n, m, minPath, edge[nmax][nmax], mark[nmax];//结点数,边数,最小路径,邻接矩阵,结点访问标记
  9. void dfs(int cur, int dst){
  10. /***operation***/
  11. /***operation***/
  12. if(minPath < dst) return;//当前走过路径大于之前最短路径,没必要再走下去
  13. if(cur == n){//临界条件
  14. if(minPath > dst) minPath = dst;
  15. return;
  16. }
  17. else{
  18. int i;
  19. for(i = 1; i <= n; i++){
  20. if(edge[cur][i] != inf && edge[cur][i] != 0 && mark[i] == 0){
  21. mark[i] = 1;
  22. dfs(i, dst+edge[cur][i]);
  23. mark[i] = 0;
  24. }
  25. }
  26. return;
  27. }
  28. }
  29. int main(){
  30. while(cin >> n >> m && n != 0){
  31. //初始化邻接矩阵
  32. int i, j;
  33. for(i = 1; i <= n; i++){
  34. for(j = 1; j <= n; j++){
  35. edge[i][j] = inf;
  36. }
  37. edge[i][i] = 0;
  38. }
  39. int a, b;
  40. while(m--){
  41. cin >> a >> b;
  42. cin >> edge[a][b];
  43. }
  44. //以dnf(1)为起点开始递归遍历
  45. memset(mark, 0, sizeof(mark));
  46. minPath = inf;
  47. mark[1] = 1;
  48. dfs(1, 0);
  49. cout << minPath << endl;
  50. }
  51. return 0;
  52. }
程序运行结果如下:



2),弗洛伊德算法(解决多源最短路径):时间复杂度O(n^3),空间复杂度O(n^2)
基本思想:最开始只允许经过1号顶点进行中转,接下来只允许经过1号和2号顶点进行中转......允许经过1~n号所有顶点进行中转,来不断动态更新任意两点之间的最短路程。即求从i号顶点到j号顶点只经过前k号点的最短路程。

分析如下:1,首先构建邻接矩阵Floyd[n+1][n+1],假如现在只允许经过1号结点,求任意两点间的最短路程,很显然Floyd[i][j] = min{Floyd[i][j], Floyd[i][1]+Floyd[1][j]},代码如下:

  1. for(i = 1; i <= n; i++){
  2. for(j = 1; j <= n; j++){
  3. if(Floyd[i][j] > Floyd[i][1] + Floyd[1][j])
  4. Floyd[i][j] = Floyd[i][1] + Floyd[1][j];
  5. }
  6. }
2,接下来继续求在只允许经过1和2号两个顶点的情况下任意两点之间的最短距离,在已经实现了从i号顶点到j号顶点只经过前1号点的最短路程的前提下,现在再插入第2号结点,来看看能不能更新更短路径,故只需在步骤1求得的Floyd[n+1][n+1]基础上,进行Floyd[i][j] = min{Floyd[i][j], Floyd[i][2]+Floyd[2][j]};......
3,很显然,需要n次这样的更新,表示依次插入了1号,2号......n号结点,最后求得的Floyd[n+1][n+1]是从i号顶点到j号顶点只经过前n号点的最短路程。故核心代码如下:

  1. #define inf 99999999
  2. for(k = 1; k <= n; k++){
  3. for(i = 1; i <= n; i++){
  4. for(j = 1; j <= n; j++){
  5. if(Floyd[i][k] < inf && Floyd[k][j] < inf && Floyd[i][j] > Floyd[i][k] + Floyd[k][j])
  6. Floyd[i][j] = Floyd[i][k] + Floyd[k][j];
  7. }
  8. }
  9. }
例1:寻找最短的从商店到赛场的路线。其中商店在1号结点处,赛场在n号结点处,1~n结点中有m条线路双向连接。

  1. /***先输入n,m,再输入m个三元组,n为路口数,m表示有几条路其中1为商店,n为赛场,三元组分别表起点,终点,该路径长,输出1到n的最短路径***/
  2. #include <iostream>
  3. using namespace std;
  4. #define inf 99999999
  5. #define nmax 110
  6. int edge[nmax][nmax], n, m;
  7. int main(){
  8. while(cin >> n >> m && n!= 0){
  9. //构建邻接矩阵
  10. int i, j;
  11. for(i = 1; i <= n; i++){
  12. for(j = 1; j <= n; j++){
  13. edge[i][j] = inf;
  14. }
  15. edge[i][i] = 0;
  16. }
  17. while(m--){
  18. cin >> i >> j;
  19. cin >> edge[i][j];
  20. edge[j][i] = edge[i][j];
  21. }
  22. //使用弗洛伊德算法
  23. int k;
  24. for(k = 1; k <= n; k++){
  25. for(i = 1; i <= n; i++){
  26. for(j = 1; j <= n; j++){
  27. if(edge[i][k] < inf && edge[k][j] < inf && edge[i][j] > edge[i][k] + edge[k][j])
  28. edge[i][j] = edge[i][k] + edge[k][j];
  29. }
  30. }
  31. }
  32. cout << edge[1][n] << endl;
  33. }
  34. return 0;
  35. }
程序运行结果如下:



3),迪杰斯特拉算法(解决单源最短路径)
基本思想:每次找到离源点(如1号结点)最近的一个顶点,然后以该顶点为中心进行扩展,最终得到源点到其余所有点的最短路径。
基本步骤:1,设置标记数组book[]:将所有的顶点分为两部分,已知最短路径的顶点集合P和未知最短路径的顶点集合Q,很显然最开始集合P只有源点一个顶点。book[i]为1表示在集合P中;
2,设置最短路径数组dst[]并不断更新:初始状态下,令dst[i] = edge[s][i](s为源点,edge为邻接矩阵),很显然此时dst[s]=0,book[s]=1。此时,在集合Q中可选择一个离源点s最近的顶点u加入到P中。并依据以u为新的中心点,对每一条边进行松弛操作(松弛是指由结点s-->j的途中可以经过点u,并令dst[j]=min{dst[j], dst[u]+edge[u][j]}),并令book[u]=1;
3,在集合Q中再次选择一个离源点s最近的顶点v加入到P中。并依据v为新的中心点,对每一条边进行松弛操作(即dst[j]=min{dst[j], dst[v]+edge[v][j]}),并令book[v]=1;
4,重复3,直至集合Q为空。
以下是图示:


核心代码如下所示:

  1. #define inf 99999999
  2. /***构建邻接矩阵edge[][],且1为源点***/
  3. for(i = 1; i <= n; i++) dst[i] = edge[1][s];
  4. for(i = 1; i <= n; i++) book[i] = 0;
  5. book[1] = 1;
  6. for(i = 1; i <= n-1; i++){
  7. //找到离源点最近的顶点u,称它为新中心点
  8. min = inf;
  9. for(j = 1; j <= n; j++){
  10. if(book[j] == 0 && dst[j] < min){
  11. min = dst[j];
  12. u = j;
  13. }
  14. }
  15. book[u] = 1;
  16. //更新最短路径数组
  17. for(k = 1; k <= n; k++){
  18. if(edge[u][k] < inf && book[k] == 0){
  19. if(dst[k] > dst[u] + edge[u][k])
  20. dst[k] = dst[u] + edge[u][k];
  21. }
  22. }
  23. }
例1:给你n个点,m条无向边,每条边都有长度d和花费p,给你起点s,终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。
输入:输入n,m,点的编号是1~n,然后是m行,每行4个数 a,b,d,p,表示a和b之间有一条边,且其长度为d,花费为p。最后一行是两个数s,t;起点s,终点 t。n和m为 0 时输入结束。(1<n<=1000, 0<m<100000, s != t)
输出:输出一行,有两个数, 最短距离及其花费。
分析:由于每条边有长度d和花费p,最好构建边结构体存放,此外可以使用邻接链表,使用邻接链表时需要将上面的核心代码修改几个地方:

1,初始化dst[]时使用结点1的邻接链表;
2,更新最短路径数组时,k的范围由1~n变为1~edge[u].size()。先采用邻接矩阵解决此题,再使用邻接表解决此题,两种方法的思路都一样:初始化邻接矩阵或邻接链表,并
初始化最短路径数组dst ----> n-1轮边的松弛中,先找到离新源点最近的中心点u,之后根据中心点u为转折点来更新路径数组。

使用邻接矩阵求解:

  1. /***对于无向图,输入n,m,点的编号是1~n,然后是m行,每行4个数 a,b,d,p,表示a和b之间有一条边,且其长度为d,花费为p。最后一行是两个数s,t;起点s,终点 t。***/
  2. /***n和m为 0 时输入结束。(1<n<=1000, 0<m<100000, s != t) 输出:输出一行,有两个数, 最短距离及其花费。***/
  3. #include <iostream>
  4. #include <iomanip>
  5. using namespace std;
  6. #define nmax 1001
  7. #define inf 99999999
  8. struct Edge{
  9. int len;
  10. int cost;
  11. };
  12. Edge edge[nmax][nmax];
  13. int dst[nmax], spend[nmax], book[nmax], n, m, stNode, enNode;
  14. int main(){
  15. while(cin >> n >> m && n != 0 && m != 0){
  16. int a, b, i, j;
  17. //构建邻接矩阵和最短路径数组
  18. for(i = 1; i <= n; i++){
  19. for(j = 1; j <= n; j++){
  20. edge[i][j].cost = 0;
  21. edge[i][j].len = inf;
  22. }
  23. edge[i][i].len = 0;
  24. }
  25. while(m--){
  26. cin >> a >> b;
  27. cin >> edge[a][b].len >> edge[a][b].cost;
  28. edge[b][a].len = edge[a][b].len;
  29. edge[b][a].cost = edge[a][b].cost;
  30. }
  31. cin >> stNode >> enNode;
  32. for(i = 1; i <= n; i++){
  33. dst[i] = edge[stNode][i].len;
  34. spend[i] = edge[stNode][i].cost;
  35. }
  36. memset(book, 0, sizeof(book));
  37. book[stNode] = 1;
  38. //开始迪杰斯特拉算法,进行剩余n-1次松弛
  39. int k;
  40. for(k = 1; k <= n-1; k++){
  41. //找离源点最近的顶点u
  42. int minNode, min = inf;
  43. for(i = 1; i <= n; i++){
  44. if(book[i] == 0 && min > dst[i] /* || min == dst[i]&& edge[stNode][min].cost > edge[stNode][i].cost*/){
  45. min = dst[i];
  46. minNode = i;
  47. }
  48. }
  49. //cout << setw(2) << minNode;
  50. book[minNode] = 1;//易错点1,错写成book[i]=1
  51. //以中心点u为转折点来更新路径数组和花费数组
  52. for(i = 1; i <= n; i++){
  53. if(book[i] == 0 && dst[i] > dst[minNode] + edge[minNode][i].len || dst[i] == dst[minNode] + edge[minNode][i].len && spend[i] > spend[minNode] + edge[minNode][i].cost){
  54. dst[i] = dst[minNode] + edge[minNode][i].len;//易错点2,错写成dst[i]+
  55. spend[i] = spend[minNode] + edge[minNode][i].cost;
  56. }
  57. }
  58. }
  59. cout << dst[enNode] << setw(3) << spend[enNode] << endl;
  60. }
  61. return 0;
  62. }
程序运行结果如下:



使用邻接链表求解:

  1. /***对于无向图,输入n,m,点的编号是1~n,然后是m行,每行4个数 a,b,d,p,表示a和b之间有一条边,且其长度为d,花费为p。最后一行是两个数s,t;起点s,终点 t。***/
  2. /***n和m为 0 时输入结束。(1<n<=1000, 0<m<100000, s != t) 输出:输出一行,有两个数, 最短距离及其花费。***/
  3. #include <iostream>
  4. #include <iomanip>
  5. #include <vector>
  6. using namespace std;
  7. #define nmax 1001
  8. #define inf 99999999
  9. struct Edge{
  10. int len;
  11. int cost;
  12. int next;
  13. };
  14. vector<Edge> edge[nmax];
  15. int dst[nmax], spend[nmax], book[nmax], n, m, stNode, enNode;
  16. int main(){
  17. while(cin >> n >> m && n != 0 && m != 0){
  18. int a, b, i, j;
  19. //构建邻接表和最短路径数组
  20. for(i = 1; i <= n; i++) edge[i].clear();
  21. while(m--){
  22. Edge tmp;
  23. cin >> a >> b;
  24. tmp.next = b;
  25. cin >> tmp.len >> tmp.cost;
  26. edge[a].push_back(tmp);
  27. tmp.next = a;
  28. edge[b].push_back(tmp);
  29. }
  30. cin >> stNode >> enNode;
  31. for(i = 1; i <= n; i++) dst[i] = inf; //注意2,别忘记写此句来初始化dst[]
  32. for(i = 0; i < edge[stNode].size(); i++){//注意1,从下标0开始存元素,误写成i <= edge[stNode].size()
  33. dst[edge[stNode][i].next] = edge[stNode][i].len;
  34. //cout << dst[2] << endl;
  35. spend[edge[stNode][i].next] = edge[stNode][i].cost;
  36. }
  37. memset(book, 0, sizeof(book));
  38. book[stNode] = 1;
  39. //开始迪杰斯特拉算法,进行剩余n-1次松弛
  40. int k;
  41. for(k = 1; k <= n-1; k++){
  42. //找离源点最近的顶点u
  43. int minnode, min = inf;
  44. for(i = 1; i <= n; i++){
  45. if(book[i] == 0 && min > dst[i] /* || min == dst[i]&& edge[stnode][min].cost > edge[stnode][i].cost*/){
  46. min = dst[i];
  47. minnode = i;
  48. }
  49. }
  50. //cout << setw(2) << minnode;
  51. book[minnode] = 1;//易错点1,错写成book[i]=1
  52. //以中心点u为转折点来更新路径数组和花费数组
  53. for(i = 0; i < edge[minnode].size(); i++){
  54. int t = edge[minnode][i].next;//别忘了加此句,表示与结点minnode相邻的点
  55. if(book[t] == 0 && dst[t] > dst[minnode] + edge[minnode][i].len || dst[t] == dst[minnode] + edge[minnode][i].len && spend[t] > spend[minnode] + edge[minnode][i].cost){
  56. dst[t] = dst[minnode] + edge[minnode][i].len;
  57. spend[t] = spend[minnode] + edge[minnode][i].cost;
  58. }
  59. }
  60. }
  61. cout << dst[enNode] << setw(3) << spend[enNode] << endl;
  62. }
  63. return 0;
  64. }
程序运行结果如下:


使用邻接表时,注意更新dst[],book[]时要使用邻接表元素对应下标中的next成员,而涉及到权值加减时时需要使用邻接表中的对应下标来取得权值;而使用邻接矩阵就没这么多顾虑了,因为这时候邻接矩阵对应下标和dst[]要更新元素的下标正好一致,都是从1开始编号。



4),Bellman-Ford算法(解决负权边,解决单源最短路径,前几种方法不能求含负权边的图)::时间复杂度O(nm),空间复杂度O(m)
主要思想:对所有的边进行n-1轮松弛操作,因为在一个含有n个顶点的图中,任意两点之间的最短路径最多包含n-1边。换句话说,第1轮在对所有的边进行松弛后,得到的是从1号顶点只能经过一条边到达其余各定点的最短路径长度。第2轮在对所有的边进行松弛后,得到的是从1号顶点只能经过两条边到达其余各定点的最短路径长度,......
以下是图示:


此外,Bellman_Ford还可以检测一个图是否含有负权回路:如果在进行n-1轮松弛后仍然存在dst[e[i]] > dst[s[i]]+w[i]。算法核心代码如下:

  1. #define inf 999999999
  2. for(i = 1; i <= n; i++) dst[i] = inf;
  3. dst[1] = 0;
  4. for(k = 1; k <= n-1; k++){
  5. for(i = 1; i <= m; i++){
  6. if(dst[e[i]] > dst[s[i]] + w[i])
  7. dst[e[i]] = dst[s[i]] + w[i];
  8. }
  9. }
  10. //检测负权回路
  11. flag = 0;
  12. for(i = 1; i <= m; i++){
  13. if(dst[e[i]] > dst[s[i]] + w[i])
  14. flag = 1;
  15. }
  16. if(flag) cout << "此图含有负权回路";
例1:对图示中含负权的有向图,输出从结点1到各结点的最短路径,并判断有无负权回路。

  1. /***先输入n,m,分别表结点数和边数,之后输入m个三元组,各表起点,终点,边权,输出1号结点到各结点的最短路径****/
  2. #include <iostream>
  3. #include <iomanip>
  4. using namespace std;
  5. #define nmax 1001
  6. #define inf 99999999
  7. int n, m, s[nmax], e[nmax], w[nmax], dst[nmax];
  8. int main(){
  9. while(cin >> n >> m && n != 0 && m != 0){
  10. int i, j;
  11. //初始化三个数组:起点数组s[],终点数组e[],权值数组w[],最短路径数组dst[]
  12. for(i = 1; i <= m; i++)
  13. cin >> s[i] >> e[i] >> w[i];
  14. for(i = 1; i <= n; i++)
  15. dst[i] = inf;
  16. dst[1] = 0;
  17. //使用Bellman_Ford算法
  18. for(j = 1; j <= n-1; j++){
  19. for(i = 1; i <= m; i++){
  20. if(dst[e[i]] > dst[s[i]] + w[i])
  21. dst[e[i]] = dst[s[i]] + w[i];
  22. }
  23. }
  24. //测试是否有负权回路并输出
  25. int flag = 0;
  26. for(i = 1; i <= m; i++)
  27. if(dst[e[i]] > dst[s[i]] + w[i])
  28. flag = 1;
  29. if(flag) cout << "此图含有负权回路\n";
  30. else{
  31. for(i = 1; i <= n; i++){
  32. if(i == 1)
  33. cout << dst[i];
  34. else
  35. cout << setw(3) << dst[i];
  36. }
  37. cout << endl;
  38. }
  39. }
  40. return 0;
  41. }
程序运行结果如下:






声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/weixin_40725706/article/detail/647787
推荐阅读
相关标签
  

闽ICP备14008679号