devbox
Monodyee
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

图论——最短路_图论最短路样例

作者：Monodyee | 2024-03-15 18:37:00

赞

踩

图论最短路样例

目录

一、Dijkstra算法

 1、朴素Dijkstra算法 

2、堆优化Dijkstra算法

二、Bellman_ford算法

三、spfa算法

1、 spfa求最短路

2.spfa判断负环

 四、Floyd算法

一、Dijkstra算法

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式

第一行包含整数 n 和 m。

接下来 mm 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

数据范围

1≤n≤500,
1≤m≤10 5,
图中涉及边长均不超过10000。

输入样例：

  1. 3 3
  2. 1 2 2
  3. 2 3 1
  4. 1 3 4

输出样例：

3

 1、朴素Dijkstra算法 

Dijkstra 的整体思路比较清晰
即进行n（n为n的个数）次迭代去确定每个点到起点的最小值 最后输出的终点的即为我们要找的最短路的距离

所以按照这个思路除了存储图外我们还需要存储两个量

  1. dist[n] //用于存储每个点到起点的最短距离
  2. st[n]   //用于在更新最短距离时 判断当前的点的最短距离是否确定 是否需要更新

每次迭代的过程中我们都先找到当前未确定的最短距离的点中距离最短的点
（至于为什么是这样那么这就涉及到Dijkstra算法的具体数学证明了 有兴趣的同学可以百度一下）

  1. int t=-1;       //将t设置为-1 因为Dijkstra算法适用于不存在负权边的图
  2. for(int j=1;j<=n;j++)
  3. {
  4.     if(!st[j]&&(t==-1||dist[t]>dist[j])    //该步骤即寻找还未确定最短路的点中路径最短的点
  5.         t=j;
  6. }


通过上述操作当前我们的t代表就是剩余未确定最短路的点中 路径最短的点
而与此同时该点的最短路径也已经确定我们将该点标记

st[t]=true;

然后用这个去更新其余未确定点的最短距离

  1. for(int j=1;j<=n;j++)
  2.     dist[j]=min(dist[j],dist[t]+g[t][j]);
  3. //这里可能有同学要问j如果从1开始的话 会不会影响之前已经确定的点的最小距离
  4. //但其实是不会 因为按照我们的Dijkstra算法的操作顺序 先确定最短距离的点的距离已经比后确定的要小 所以不会影响
  5. //当然你也可以在循环判断条件里加上if(!st[i])
  6. //这里j从1开始只是为了代码的简洁

进行n次迭代后最后就可以确定每个点的最短距离
然后再根据题意输出相应的 要求的最短距离

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=510;
  4. int dist[N];     //用于记录每一个点距离第一个点的距离
  5. int g[N][N];     //稠密图一般使用邻接矩阵
  6. bool st[N];      //用于记录该点的最短距离是否已经确定
  7. int n,m;
  8.  
  9. int dijkstra()
  10. {
  11.     //所有节点距离起点的距离初始化为无穷大
  12.     memset(dist,0x3f,sizeof dist);  
  13.     //起点距离自己的距离为零
  14.     dist[1] = 0;
  15.     
  16.     //迭代n次，每次可以确定一个点到起点的最短路
  17.     for(int i=0;i<n;i++)
  18.     {
  19.         
  20.         int t=-1;   //t存储当前访问的点
  21.         
  22.         for (int j = 1; j <= n; j++) //这里的j代表的是从1号点开始
  23.         {
  24.             //不在st集合中，并且
  25.             //如果没有更新过，则进行更新， 或者发现更短的路径，则进行更新
  26.             if (!st[j] && (t == -1 || dist[j] < dist[t])) 
  27.             {
  28.                 t = j;
  29.             }
  30.         }
  31.           //加入到st集合中
  32.         st[t] = true;
  33.  
  34.         //找到了距离最小的点t，并用最小的点t去更新其他的点到起点的距离
  35.         for (int j = 1; j <= n; ++j) 
  36.         {
  37.             dist[j] = min(dist[j], dist[t] + g[t][j]);
  38.         }
  39.     }
  40.  
  41.     // 如果起点到达不了n号节点，则返回-1
  42.     if (dist[n] == 0x3f3f3f3f) return -1;
  43.     // 返回起点距离n号节点的最短距离
  44.     return dist[n];
  45. }
  46. int main()
  47. {
  48.     cin>>n>>m;
  49.     
  50.     memset(g,0x3f,sizeof g);    //初始化图 因为是求最短路径
  51.                                 //所以每个点初始为无限大
  52.     
  53.     while(m--)
  54.     {
  55.         int a,b,c;
  56.         cin>>a>>b>>c;
  57.         g[a][b] = min(g[a][b], c); //如果有重边，请保留权值最小的一条边
  58.     }
  59.     cout << dijkstra() << endl;
  60. }

2、堆优化Dijkstra算法

注意：若要求任意点 i 到任意个点 j 的最短距离，只需修改dijkstra方法中的起源位置dist[i] = 0，以及返回为dist[j] 

  1. #include<iostream>
  2. #include<cstring>
  3. #include<algorithm>
  4. #include<queue>
  5.  
  6. using namespace std;
  7. typedef pair<int, int> PII; //<离起点的距离， 节点编号>
  8.  
  9. const int N = 150010;
  10. int h[N], e[N], ne[N], idx, w[N];
  11. int dist[N];
  12. bool st[N];
  13. int n, m;
  14.  
  15. //在a节点之后插入一个b节点，权重为c
  16. void add(int a, int b, int c) {
  17.     e[idx] = b;
  18.     w[idx] = c;
  19.     ne[idx] = h[a];
  20.     h[a] = idx++;
  21. }
  22.  
  23. int dijkstra() {
  24. //    所有距离初始化为无穷大
  25.     memset(dist, 0x3f, sizeof dist);
  26. //    1号节点距离为0
  27.     dist[1] = 0;
  28. //    建立一个小根堆
  29.     priority_queue<PII, vector<PII>, greater<PII>> heap;
  30. //    1号节点插入堆
  31.     heap.push({0, 1});
  32.     while (heap.size()) {
  33. //        取出堆顶顶点
  34.         auto t = heap.top();
  35. //        并删除
  36.         heap.pop();
  37. //        取出节点编号和节点距离
  38.         int ver = t.second, distance = t.first;
  39. //        如果节点被访问过，则跳过
  40.         if (st[ver])continue;
  41.         st[ver] = true;
  42.         for (int i = h[ver]; i != -1; i = ne[i]) {
  43. //            取出节点编号
  44.             int j = e[i];
  45. //            dist[j] 大于从t过来的距离
  46.             if (dist[j] > distance + w[i]) {
  47.  
  48.                 dist[j] = distance + w[i];
  49.                 heap.push({dist[j], j});
  50.             }
  51.         }
  52.     }
  53.     if (dist[n] == 0x3f3f3f3f)return -1;
  54.     return dist[n];
  55.  
  56. }
  57.  
  58. int main() {
  59.     memset(h, -1, sizeof h);
  60.     cin >> n >> m;
  61.     while (m--) {
  62.         int a, b, c;
  63.         cin >> a >> b >> c;
  64.         add(a, b, c);
  65.     }
  66.     cout << dijkstra() << endl;
  67.     return 0;
  68. }

二、Bellman_ford算法

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出从 1 号点到 n 号点的最多经过 kk 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。

注意：图中可能 存在负权回路 。

输入格式

第一行包含三个整数 n,m,k。

接下来 mm 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

点的编号为 1∼n。

输出格式

输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。

如果不存在满足条件的路径，则输出 impossible。

数据范围

1≤n,k≤500,
1≤m≤10000,
1≤x,y≤n，
任意边长的绝对值不超过 10000。

输入样例：

  1. 3 3 1
  2. 1 2 1
  3. 2 3 1
  4. 1 3 3

输出样例：

3

dijkstra 为什么不能解决解决负权边最短路问题


加入每条边去松弛每个点到起点的距离

dist[b] = min(dist[b], backup[a] + w);


为什么需要back[a]数组
为了避免如下的串联情况， 在边数限制为一条的情况下，节点3的距离应该是3，但是由于串联情况，利用本轮更新的节点2更新了节点3的距离，所以现在节点3的距离是2。

正确做法是用上轮节点2更新的距离--无穷大，来更新节点3， 再取最小值，所以节点3离起点的距离是3。

  1. for (int i = 0; i < k; i ++ )
  2. {
  3.     memcpy(backup, dist, sizeof dist);
  4.     for (int j = 0; j < m ; j ++ )
  5.     {
  6.         int a = edges[j].a, b = edges[j].b, w = edges[j].w;
  7.         dist[b] = min(dist[b], backup[a] + w);
  8.     }
  9. }


为什么是dist[n]>0x3f3f3f3f/2， 而不是dist[n]>0x3f3f3f3f
5号节点距离起点的距离是无穷大，利用5号节点更新n号节点距离起点的距离，将得到109−2109−2, 虽然小于109109, 但并不存在最短路，(在边数限制在k条的条件下)。

  1. if(dist[n]>0x3f3f3f3f/2) return -1;
  2. else return dist[n];
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=510,M=10010;
  4.  
  5. int dist[N];
  6. int backup[N];  //备份数组防止串联
  7. int n,m,k;      //k代表最短路径最多包涵k条边
  8.  
  9. struct Edge
  10. {
  11.     int a,b,w;
  12. }edge[M];      //把每个边保存下来即可
  13.  
  14. int bellman_ford()
  15. {
  16.     memset(dist,0x3f,sizeof dist);
  17.     dist[1]=0;
  18.     for(int i=0;i<k;i++)
  19.     {
  20.         memcpy(backup,dist,sizeof dist);
  21.         for(int j=0;j<m;j++)//遍历所有边
  22.         {
  23.             int a=edge[j].a,b=edge[j].b,w=edge[j].w;
  24.            dist[b] = min(dist[b], backup[a] + w);
  25.            //使用backup:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来
  26.         }
  27.     }
  28.     
  29.     return dist[n];
  30. }
  31. int main()
  32. {
  33.     cin>>n>>m>>k;
  34.     for(int i=0;i<m;i++)
  35.     cin>>edge[i].a>>edge[i].b>>edge[i].w;
  36.     int t=bellman_ford();
  37.     if(dist[n] > 0x3f3f3f3f / 2)
  38.     puts("impossible");
  39.     else 
  40.     cout<<t;
  41.     return 0;
  42. }

三、spfa算法


1、 spfa求最短路

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。

数据保证不存在负权回路。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 impossible。

数据范围

1≤n,m≤10 5,
图中涉及边长绝对值均不超过 10000。

输入样例：

  1. 3 3
  2. 1 2 5
  3. 2 3 -3
  4. 1 3 4

输出样例：

2

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=1e5+10;
  4. int n,m;
  5. int h[N],w[N],e[N],ne[N],idx;//邻接表，存储图
  6. int dist[N];
  7. int st[N];
  8.  
  9.  
  10. void add(int a,int b,int c)
  11. {
  12.     e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
  13. }
  14.  
  15. int spfa()
  16. {
  17.     memset(dist,0x3f,sizeof dist);
  18.     dist[1]=0;
  19.     queue<int> q;
  20.     q.push(1);
  21.     st[1]=true;
  22.     
  23.     while(q.size())
  24.     {
  25.         int t=q.front();
  26.         q.pop();
  27.         st[t]=false;//从队列中取出来之后该节点st被标记为false,代表之后该节点如果发生更新可再次入队
  28.         
  29.         for(int i=h[t];i!=-1;i=ne[i])
  30.         {
  31.              int j=e[i];
  32.             if(dist[j]>dist[t]+w[i])
  33.             {
  34.                 dist[j]=dist[t]+w[i];
  35.                 if(!st[j])//当前已经加入队列的结点，无需再次加入队列，即便发生了更新也只用更新数值即可，重复添加降低效率
  36.                 {
  37.                     q.push(j);
  38.                     st[j]=true;
  39.                     
  40.                 }
  41.             }
  42.         }
  43.     }
  44.  
  45.     return dist[n];
  46. }
  47. int main()
  48. {
  49.     cin>>n>>m;
  50.     memset(h,-1,sizeof h);
  51.     while(m--)
  52.     {
  53.         int a,b,c;
  54.         cin>>a>>b>>c;
  55.         add(a,b,c);
  56.     }
  57.     int t=spfa();
  58.     if(t==0x3f3f3f3f)
  59.     puts("impossible");
  60.     else
  61.     cout<<t;
  62.     return 0;
  63. }

2.spfa判断负环

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N=1e5+10;
  4. int n,m;
  5. int h[N],w[N],e[N],ne[N],idx;//邻接表，存储图
  6. int dist[N],cnt[N];
  7. int st[N];
  8.  
  9.  
  10. void add(int a,int b,int c)
  11. {
  12.     e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
  13. }
  14.  
  15. int spfa()
  16. {
  17.     queue<int> q;
  18.     
  19.     for(int i=1;i<=n;i++)
  20.     {
  21.         st[i]=true;
  22.         q.push(i);
  23.     }
  24.     
  25.     while(q.size())
  26.     {
  27.         int t=q.front();
  28.         q.pop();
  29.         st[t]=false;//从队列中取出来之后该节点st被标记为false,代表之后该节点如果发生更新可再次入队
  30.         
  31.         for(int i=h[t];i!=-1;i=ne[i])
  32.         {
  33.              int j=e[i];
  34.             if(dist[j]>dist[t]+w[i])
  35.             {
  36.                 dist[j]=dist[t]+w[i];
  37.                 cnt[j]=cnt[t]+1;
  38.                 if(cnt[j]>=n)return true;
  39.                 if(!st[j])//当前已经加入队列的结点，无需再次加入队列，即便发生了更新也只用更新数值即可，重复添加降低效率
  40.                 {
  41.                     q.push(j);
  42.                     st[j]=true;
  43.                     
  44.                 }
  45.             }
  46.         }
  47.     }
  48.  
  49.     return false;
  50. }
  51. int main()
  52. {
  53.     cin>>n>>m;
  54.     memset(h,-1,sizeof h);
  55.     while(m--)
  56.     {
  57.         int a,b,c;
  58.         cin>>a>>b>>c;
  59.         add(a,b,c);
  60.     }
  61.     if(spfa())
  62.     puts("Yes");
  63.     else
  64.     puts("No");
  65.     return 0;
  66. }

 四、Floyd算法

多源汇最短路问题-具有多个源点
Floyd算法 O(n^3)-动态规划
给定一个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≤2001≤n≤200
1≤k≤n21≤k≤n2
1≤m≤200001≤m≤20000
图中涉及边长绝对值均不超过10000。

输入样例：
3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3
输出样例：
impossible
1

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N=210,INF=1e9;
  5. int n,m,Q;
  6. int d[N][N];
  7.  
  8. void floyd()
  9. {
  10.     for(int k=1;k<=n;k++)
  11.     for(int i=1;i<=n;i++)
  12.     for(int j=1;j<=n;j++)
  13.     d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
  14. }
  15. int main()
  16. {
  17.     cin>>n>>m>>Q;
  18.     for(int i=1;i<=n;i++)
  19.     for(int j=1;j<=n;j++)
  20.     if(i==j)
  21.     d[i][j]=0;
  22.     else
  23.     d[i][j]=INF;
  24.     while(m--)
  25.     {
  26.         int a,b,w;
  27.         cin>>a>>b>>w;
  28.         d[a][b]=min(d[a][b],w);
  29.         //注意保存最小的边
  30.     }
  31.     floyd();
  32.     while(Q--)
  33.     {
  34.         int a,b;
  35.         cin>>a>>b;
  36.         if(d[a][b]>INF/2)//由于有负权边存在所以约大过INF/2也很合理
  37.         puts("impossible");
  38.         else
  39.         cout<<d[a][b]<<endl;
  40.     }
  41.     return 0;
  42. }

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

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号