经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » 数据库/运维 » Windows » 查看文章
图论-最短路径<Dijkstra,Floyd>
来源：cnblogs　　作者：御·Dragon　　时间：2019/10/29 10:20:15　　对本文有异议

昨天： 图论-概念与记录图的方法

以上是昨天的Blog，有需要者请先阅读完以上再阅读今天的Blog。

可能今天的有点乱，好好理理，认真看完相信你会懂得

分割线

第二天

引子：昨天我们简单讲了讲图的概念与记录图的方法，那么大家有一定的底子了，我们就开始初步接触图论算法了！

我们只讲Dijkstra和Floyd，因为其实在比赛中会这两个算法就很好了。

今天我们要讲的是：最短路径问题

Top1：最短路的概念

相信大家都知道有一款Made in China的导航软件——百度导航。那么他们是怎么为我们导航的？就是使用了今天我们要学的问题 最短路径 。

说不定你学了之后就可以做一个导航的 是不是有点小激动？

$\color{red}\text{ 重点：最短路问题就是一个点到另一个最短的路径！ }$

最短路专业术语：

松弛： 既然求一个点到另一个点最短的路径，那么肯定就会有更优的路径替代目前路径的操作。这就叫做 松弛操作。

中转点： 一个点到另一个点不一定是有直接道路连接的，可能会经过一些别的点，我们就叫那些点叫做 中转点 。

Top2:Floyd算法

现在大家都知道最短路是什么了，那么从简单到复杂，我们先来看看新手必懂的算法。

Floyd简单粗暴，就是枚举三个点，一个起点，一个终点，一个中转点。看 起点到中转点的路径 加上 中转点到终点的路径 是不是小于 目前起点到终点的路径 即可（就是不断松弛）。

显而易见，Floyd算法很好懂，就是时间复杂度高了点—— $N^3$ 的复杂度。而且，Floyd是多源最短路，询问时只需调用dis就行了。

所以， 当 N 大于1000时，慎用！

代码就很简答啦(蒟蒻用邻接矩阵写的)：

  1. //如果为无向图,dis就会对称,Floyed的j就只要到i,且dis[i][j]dis[j][i] 要一起更新 
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. const int MAXN = 1000 + 10;
  5. int n,m;
  6. int x,y,z;
  7. int dis[MAXN][MAXN];
  8. void Floyd(){
  9.     for(int k = 1;k <= n; k++)
  10.         for(int i = 1;i <= n; i++)
  11.             for(int j = 1;j <= n/*i*/; j++)
  12.                 if(dis[i][k] + dis[k][j] < dis[i][j])dis[i][j] = dis[i][k] + dis[k][j];
  13.     return;
  14. }
  15. int main(){
  16.     cin>>n>>m;
  17.     for(int i = 1;i <= n; i++)dis[i][i] = 0;
  18.     for(int i = 1;i <= n; i++)
  19.         for(int j = 1;j <= n; j++){
  20.             if(i != j)dis[i][j] = 1e9;
  21.         }
  22.     for(int i = 1;i <= m; i++){
  23.         cin>>x>>y>>z;
  24.         dis[x][y] = z;
  25.     }
  26.     Floyd();
  27.     for(int i = 1;i <= n; i++){
  28.         for(int j = 1;j <= n; j++){
  29.             cout<<dis[i][j]<<" ";
  30.         }
  31.         cout<<endl;
  32.     }
  33.     return 0;
  34. }

分割线

分割线

Top3：Dijkstra算法

Dijkstra与Floyd相反，是单元最短路，即只能求出一个点到其他所有点的最短路。

Dijkstra属于贪心的思想，正解：

首先定义两个种类——黑点和白点，黑点就是在目前算完最短路径的点，白点反之。

每次在白点中找一个离目前任意一个黑点最近的，加入黑点，更新白点到原点的最短路即可。

代码如下：注意：这里的dis不再是邻接矩阵，是单源最短路径。tot才是邻接矩阵！

邻接矩阵，蒟蒻是用洛谷P1828 香甜的黄油 Sweet Butter 作为例题写的模板，体谅一下

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int MAXN = 100 + 10;
  4. struct Node{
  5.     int x,y;
  6. }f[MAXN];
  7. int n,m,a,b,s,t;
  8. bool black[MAXN];
  9. double dis[MAXN];
  10. double tot[MAXN][MAXN];
  11. double calc(int i,int j){
  12.     return sqrt((f[i].x - f[j].x) * (f[i].x - f[j].x) + (f[i].y - f[j].y) * (f[i].y - f[j].y));
  13. }
  14. double Dijkstra(int start,int end){
  15.     for(int i = 1;i <= n; i++){
  16.         dis[i] = tot[start][i];
  17.     }
  18.     dis[start] = 0;
  19.     black[start] = true;
  20.     for(int i = 1;i < n; i++){
  21.         double M = 2e9;
  22.         int u = start;
  23.         for(int j = 1;j <= n; j++){
  24.             if(dis[j] < M && !black[j]){
  25.                 M = dis[j];
  26.                 u = j;
  27.             }
  28.         }
  29.         if(u == start)continue;
  30.         //此处的判断与前面的u = start对应,若该图存在一个单独的点这里就要加上
  31.         //否则可以u = 0,这个判断删掉 
  32.         black[u] = true;
  33.         for(int j = 1;j <= n; j++){
  34.             if(black[j])continue;
  35.             if(dis[u] + tot[u][j] < dis[j]){
  36.                 dis[j] = dis[u] + tot[u][j];
  37.             }
  38.         }
  39.     }
  40.     return dis[end];
  41. } 
  42. int main(){
  43.     scanf("%d",&n);
  44.     for(int i = 1;i <= n; i++)
  45.         for(int j = 1;j <= n; j++){
  46.             tot[i][j] = i == j ? 0 : 1e9;
  47.         }
  48.     for(int i = 1;i <= n; i++){
  49.         scanf("%d%d",&f[i].x,&f[i].y);
  50.     }
  51.     scanf("%d",&m);
  52.     for(int i = 1;i <= m; i++){
  53.         scanf("%d%d",&a,&b);
  54.         tot[a][b] = calc(a,b);
  55.         tot[b][a] = tot[a][b];
  56.     }
  57.     scanf("%d%d",&s,&t);
  58.     printf("%.2f",Dijkstra(s,t));
  59.     return 0;
  60. }

所以，Dijkstra的时间复杂度是 $N^2$

怎么优化呢？很简单——在寻找离黑点最近的白点时，使用优先队列即可。

优先队列Dijkstra：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int MAXN = 800 + 10;
  4. const int MAX = 1e9;
  5. int n,m,p,x,y,z;
  6. int a[MAXN];
  7. int dis[MAXN];
  8. int tot[MAXN][MAXN];
  9. vector<int> nei[MAXN];
  10. struct Node{
  11.     int num,dist;
  12.     bool operator < (const Node& next) const {
  13.         return dist > next.dist;
  14.     }
  15. };
  16. void Dijkstra(int start){
  17.     priority_queue <Node> cow;
  18.     for(int i = 1;i <= n; i++){
  19.         dis[i] = 2e9;
  20.     }
  21.     dis[start] = 0;
  22.     Node tt = {start,0};
  23.     cow.push(tt);
  24.     while(!cow.empty()){
  25.         tt = cow.top();
  26.         cow.pop();
  27.         int u = tt.num;
  28.         for(int i = 0;i < nei[u].size(); i++){
  29.             int p = nei[u][i];
  30.             if(dis[u] + tot[u][p] < dis[p]){
  31.                 dis[p] = dis[u] + tot[u][p];
  32.                 Node next;
  33.                 next.num = p;
  34.                 next.dist = dis[p];
  35.                 cow.push(next);
  36.             }
  37.         }
  38.     }
  39.     return;
  40. } 
  41. int main(){
  42.     scanf("%d%d%d",&n,&m);
  43.     for(int i = 1;i <= n; i++)
  44.         for(int j = 1;j <= i; j++){
  45.             tot[i][j] = tot[j][i] = i == j ? 0 : MAX;
  46.         }
  48.     for(int i = 1;i <= m; i++){
  49.         scanf("%d%d%d",&x,&y,&z);
  50.         tot[x][y] = z;
  51.         tot[y][x] = z;
  52.         nei[x].push_back(y);
  53.         nei[y].push_back(x);
  54.     }
  56.     int s,t;
  57.     scanf("%d%d",&s,&t);
  58.     Dijkstra(s);
  59.     cout<<dis[t]<<"\n";
  60.     return 0;
  61. }

顺便带一下SPFA的算法模板和用动态数组记录的Dijkatra(这里不做详解了，有需要的人可以复制看一下)

SPFA：

  1. #include<iostream>
  2. #include<cmath>
  3. #include<algorithm>
  4. #include<queue>
  5. #include<cstring> 
  6. using namespace std;
  7. int n, p, c, cow[801], a, b, d, cnt = 0, sum = 0, ans = 2147483647;
  8. int dis[10000], w[10000], next[10000], to[10000], first[10000] = {0};
  9. bool exist[10000] = {false};
  10. queue<int> q;
  12. void addEdge(int u, int v, int weight)
  13. {
  14.     cnt++; //边的编号 
  15.     to[cnt] = v; //第cnt条边指向点v 
  16.     w[cnt] = weight; //第cnt条边的权值 
  17.     next[cnt] = first[u]; // 第cnt条边指向连接点u的第一条边 
  18.     first[u] = cnt; //将连接点u的第一条边更新为第cnt条边
  19.     return; 
  20. } 
  22. void spfa(int start)
  23. {
  24.     memset(exist, false, sizeof(exist)); //一开始所有点在队列外 
  25.     memset(dis, 0x7f, sizeof(dis)); //将所有点到起始点的距离置为极大值 
  26.     dis[start] = 0; 
  27.     q.push(start); //起始点入队列 
  28.     exist[start] = true; 
  29.     while(!q.empty())
  30.     {
  31.         int head = q.front(); //取队列的第一个点 
  32.         q.pop();
  33.         exist[head] = false;
  34.         for(int e = first[head]; e != 0; e = next[e]) //循环head连接的每一条边 
  35.         {
  36.             //松弛操作 
  37.             if(dis[head] + w[e] < dis[to[e]])
  38.             {
  39.                 dis[to[e]] = dis[head] + w[e];
  40.                 if(exist[to[e]] == false)
  41.                 {
  42.                     q.push(to[e]); //将被更新的点入队列 
  43.                     exist[to[e]] = true;
  44.                 }
  45.             }
  46.         }
  47.     }
  48.     return;
  49. }
  51. int main()
  52. {
  53.     cin >> n >> p >> c;
  54.     for(int i=1; i <= n; i++) //输入每头牛所在的位置 
  55.     {
  56.         cin >> cow[i];
  57.     }
  58.     for(int e=1; e <= c; e++) //输入每一条边 
  59.     {
  60.         cin >> a >> b >> d;
  61.         addEdge(a, b, d);
  62.         addEdge(b, a, d);
  63.     }
  64.     for(int i=1; i <= p; i++) //注意是循环牧场
  65.     {
  66.         spfa(i);
  67.         sum = 0;
  68.         for(int j=1; j <= n; j++)
  69.         {
  70.             sum = sum + dis[cow[j]];
  71.         }
  72.         ans = min(ans, sum);
  73.     }
  74.     cout << ans;
  75.     return 0;
  76. }

动态数组Dijkstra：

  1. #include<iostream>
  2. #include<cmath>
  3. #include<queue>
  4. #include<vector>
  5. using namespace std;
  6. int n, p, c;
  7. const int INF = 1e9;
  8. int cow[805], dis[805], vertex[805][805];
  9. vector<int> neighbor[805]; 
  11. struct Node
  12. {
  13.     int id, dist;
  14.     bool operator < (const Node & second) const
  15.     {
  16.         return dist > second.dist;
  17.     }
  18. };
  20. void dijkstra(int start)
  21. {
  22.     priority_queue<Node> pq;
  23.     for(int i = 1; i <= p; i++)
  24.     {
  25.         dis[i] = INF;
  26.     }
  27.     dis[start] = 0;
  28.     Node cur = {start, 0}; //起始点和其到dis[start] 
  29.     pq.push(cur);
  30.     while(!pq.empty())
  31.     {
  32.         cur = pq.top();
  33.         pq.pop();
  34.         int u = cur.id;
  35.         for(int i=0; i <= neighbor[u].size() - 1; i++)
  36.         {
  37.             int v = neighbor[u][i]; //与u相邻的边v 
  38.             if(dis[u] + vertex[u][v] < dis[v])
  39.             {
  40.                 dis[v] = dis[u] + vertex[u][v];
  41.                 Node next;
  42.                 next.id = v;
  43.                 next.dist = dis[v];
  44.                 pq.push(next);
  45.             }
  46.         }
  47.     }
  48.     return;
  49. } 
  51. int main()
  52. {
  53.     cin >> n >> p >> c;
  54.     for(int i = 1; i <= n; i++) //输入每头牛所在的位置 
  55.     {
  56.         cin >> cow[i];
  57.     }
  58.     for(int i=1; i <= p; i++)
  59.     {
  60.         for(int j=1; j <= p; j++)
  61.         {
  62.             vertex[i][j] = (i == j) ? 0 : INF;
  63.         }
  64.     }
  65.     for(int i=1; i <= c; i++) //输入每一条边 
  66.     {
  67.         int a, b, d;
  68.         cin >> a >> b >> d;
  69.         vertex[a][b] = d;
  70.         vertex[b][a] = d;
  71.         neighbor[a].push_back(b);
  72.         neighbor[b].push_back(a); 
  73.     }
  74.     int ans = INF;
  75.     for(int i=1; i <= p; i++) //注意是循环牧场
  76.     {
  77.         dijkstra(i); //假如把糖放在第i个牧场 
  78.         int sum = 0;
  79.         for(int j=1; j <= n; j++)
  80.         {
  81.             sum = sum + dis[cow[j]];
  82.         }
  83.         ans = min(ans, sum);
  84.     }
  85.     cout << ans;
  86.     return 0;
  87. }

好了，第二天就到这里，是不是都听懂了呢狗屁？欢迎在下方留言！

原文链接：http://www.cnblogs.com/CJYBlog/p/short-path.html

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

Windows热门文章

  • 电信中兴F460光猫sendcmd命令
  • 解决：500 Internal Privoxy Error
  • 关于破解邮箱的一点心得
  • 在Windows模拟器中使用LVGL8.3
  • win10引导错误的修复（内容系转载）
  • 我是程序猿：Windows能被感染？最常见的恶意电子邮件附件
  • 【手记】解决Intel Management Engine Interface黄色感叹号
  • win10安装OpenSSL及简单的使用
  • NT路径，DOS路径和Device路径互相转换
  • windows无人值守文件的制作_autounattend.xml

    • Windows推荐文章

  • Qt+OpenCascade开发笔记（二）：windows开发环境搭建（二）：Qt引入occ库，搭建基础工程模板Demo和发布Demo
  • 踩坑记录：windows11下使用 VS2022 和 PCL1.14.1 配置点云开发环境
  • FFmpeg开发笔记（三十五）Windows环境给FFmpeg集成libsrt
  • .NET App 与Windows系统媒体控制(SMTC)交互
  • 【Azure App Service】.NET代码实验App Service应用中获取TLS/SSL 证书 (App Service Windows)
  • 文件系统(四)：FAT32文件系统实现原理
  • FFmpeg开发笔记（十七）Windows环境给FFmpeg集成字幕库libass
  • 2024年，提升Windows开发和使用体验实践 - 终端&命令行篇
  • c# 4.8 实现Windows 定时任务计划（Task Scheduler）
  • 推荐10款C#开源好用的Windows软件

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号