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

2024/2/17 图论 最短路入门 dijkstra 1

作者：weixin_40725706 | 2024-03-04 11:17:03

赞

踩

2024/2/17 图论 最短路入门 dijkstra 1

目录

算法思路

Dijkstra求最短路

AcWing 849. Dijkstra求最短路 I - AcWing

850. Dijkstra求最短路 II - AcWing题库

最短路

最短路 - HDU 2544 - Virtual Judge (vjudge.net)

【模板】单源最短路径（弱化版）

P3371 【模板】单源最短路径（弱化版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

【模板】单源最短路径（标准版）

P4779 【模板】单源最短路径（标准版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

畅通工程续

 畅通工程续 - HDU 1874 - Virtual Judge (vjudge.net)

算法思路

dijkstra解决的是单源的最短路问题，就是一个顶点到其他顶点的最短路问题

开一个数组dist,dist[x]表示从起点出发，到x的距离

比如这幅图，初始情况下，把所有的dist都设置为inf（也就是无穷大）

dist[1]=0,dist[2]=dist[3]=inf

因为1是起点，自己到自己的距离是0

还有一个bool类型的vis数组，因为每个点只能走一次

选当前离起点最近（权值最小）且没有选过的点，来更新其它点的距离

所以如图：

第一次选1号，更新最近的2，3号点 dist[2]=2,dist[3]=4

第二次选2号（因为权值比1到3的小）  dist[2]+1<dist[3],所以dist[3]=dist[2]+1

这个样例的最短路就得到了

Dijkstra求最短路

AcWing 849. Dijkstra求最短路 I - AcWing

850. Dijkstra求最短路 II - AcWing题库

这两道题只有数据范围的差别，用下面的代码可以一次过

注意：

优先队列q里面的pair存的是dist和点数

二维数组g里面的pair存的是点数和边权

完整代码:

  1. #include <bits/stdc++.h>
  2. #define int long long
  3. const int N = 15e4+10;
  4. std::vector<std::vector<std::pair<int,int>>> g(N);
  5. #define PII std::pair<int,int>
  6. signed main()
  7. {
  8.     int n,m;
  9.     std::cin >> n >> m;
  10.     for(int i = 1;i <= m;i ++)
  11.     {
  12.         int u,v,w;
  13.         std::cin >> u >> v >> w;
  14.         g[u].push_back({v,w});
  15.     }
  16.     std::priority_queue<PII,std::vector<PII>,std::greater<>> q;
  17.     std::vector<int> dist(n+1,INT_MAX);
  18.     std::vector<bool> vis(n+1);
  19.     dist[1]=0;
  20.     q.push({0,1});//存dist和点数
  21.     while(!q.empty())
  22.     {
  23.         auto node = q.top();
  24.         q.pop();
  25.         int cur=node.second;
  26.         if(vis[cur]==true)
  27.             continue;
  28.         else
  29.         {
  30.             vis[cur]=true;
  31.             for(int i = 0;i < g[cur].size();i ++)
  32.             {
  33.                 int e=g[cur][i].first;
  34.                 int w=g[cur][i].second;
  35.                 if(dist[e]>dist[cur]+w)
  36.                 {
  37.                     dist[e]=dist[cur]+w;
  38.                     q.push({dist[e],e});
  39.                 }
  40.             }
  41.         }
  42.     }
  43.     if(dist[n]==INT_MAX)
  44.         std::cout<<-1;
  45.     else
  46.         std::cout<<dist[n];
  47.     return 0;
  48. }

最短路

最短路 - HDU 2544 - Virtual Judge (vjudge.net)

思路：dijkstra，但是需要建立双向边

注意：多组输入最好不要开全局变量，如果开全局变量记得清空

完整代码：

  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define PII std::pair<int,int>
  4. const int N = 1e4+10;
  5. signed main()
  6. {
  7.     int n,m;
  8.     while(std::cin >> n >> m)
  9.     {
  10.         if(n==0&&m==0)
  11.             break;
  12.         std::vector<std::vector<std::pair<int,int>>>g (N+1);
  13.         std::priority_queue<PII,std::vector<PII>,std::greater<>> q;
  14.         std::vector<int> dist(n+1,INT_MAX);
  15.         std::vector<bool> vis(n+1);
  16.         dist[1]=0;
  17.         for(int i = 1;i <= m;i ++)
  18.         {
  19.             int u,v,w;
  20.             std::cin >> u >> v >> w;
  21.             g[u].push_back({v,w});
  22.             g[v].push_back({u,w});
  23.         }
  24.         q.push({0,1});//存dist和点数
  25.         while(!q.empty()) {
  26.             auto node = q.top();
  27.             q.pop();
  28.             int cur = node.second;
  29.             if (vis[cur] == true)
  30.                 continue;
  31.             else {
  32.                 vis[cur] = true;
  33.                 for (int i = 0; i < g[cur].size(); i++) {
  34.                     int e = g[cur][i].first;//存点
  35.                     int w = g[cur][i].second;//存边权
  36.                     if (dist[e] > dist[cur] + w) {
  37.                         dist[e] = dist[cur] + w;
  38.                         q.push({dist[e], e});
  39.                     }
  40.                 }
  41.             }
  42.         }
  43.         std::cout<<dist[n]<<"\n";
  44.     }
  45.     return 0;
  46. }

【模板】单源最短路径（弱化版）

P3371 【模板】单源最短路径（弱化版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：dijkstra模板

完整代码：

  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define PII std::pair<int,int>
  4. const int N = 5e5+10;
  5. signed main()
  6. {
  7.     int n,m,s;
  8.     std::cin >> n >> m >> s;
  9.     std::vector<std::vector<std::pair<int,int>>> g(n+1);
  10.     std::vector<int> dist(n+1,INT_MAX);
  11.     std::vector<bool> vis(n+1);
  12.     dist[s]=0;
  13.     for(int i = 1; i <= m;i ++)
  14.     {
  15.         int u,v,w;
  16.         std::cin >> u >> v >> w;
  17.         g[u].push_back({v,w});
  18.     }
  19.     std::priority_queue<PII,std::vector<PII>,std::greater<>> q;
  20.     q.push({0,s});//存dist和点数
  21.     while(!q.empty()) {
  22.         auto node = q.top();
  23.         q.pop();
  24.         int cur = node.second;
  25.         if (vis[cur] == true)
  26.             continue;
  27.         else {
  28.             vis[cur] = true;
  29.             for (int i = 0; i < g[cur].size(); i++) {
  30.                 int e = g[cur][i].first;//存点
  31.                 int w = g[cur][i].second;//存边权
  32.                 if (dist[e] > dist[cur] + w) {
  33.                     dist[e] = dist[cur] + w;
  34.                     q.push({dist[e], e});
  35.                 }
  36.             }
  37.         }
  38.     }
  39.     for(int i = 1;i <= n;i ++)
  40.     {
  41.         std::cout<<dist[i]<<" ";
  42.     }
  43.     return 0;
  44. }
  45.

【模板】单源最短路径（标准版）

P4779 【模板】单源最短路径（标准版） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

和上一题的代码一样，只是数据范围大一点

完整代码：

  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define PII std::pair<int,int>
  4. const int N = 5e5+10;
  5. signed main()
  6. {
  7.     int n,m,s;
  8.     std::cin >> n >> m >> s;
  9.     std::vector<std::vector<std::pair<int,int>>> g(n+1);
  10.     std::vector<int> dist(n+1,INT_MAX);
  11.     std::vector<bool> vis(n+1);
  12.     dist[s]=0;
  13.     for(int i = 1; i <= m;i ++)
  14.     {
  15.         int u,v,w;
  16.         std::cin >> u >> v >> w;
  17.         g[u].push_back({v,w});
  18.     }
  19.     std::priority_queue<PII,std::vector<PII>,std::greater<>> q;
  20.     q.push({0,s});//存dist和点数
  21.     while(!q.empty()) {
  22.         auto node = q.top();
  23.         q.pop();
  24.         int cur = node.second;
  25.         if (vis[cur] == true)
  26.             continue;
  27.         else {
  28.             vis[cur] = true;
  29.             for (int i = 0; i < g[cur].size(); i++) {
  30.                 int e = g[cur][i].first;//存点
  31.                 int w = g[cur][i].second;//存边权
  32.                 if (dist[e] > dist[cur] + w) {
  33.                     dist[e] = dist[cur] + w;
  34.                     q.push({dist[e], e});
  35.                 }
  36.             }
  37.         }
  38.     }
  39.     for(int i = 1;i <= n;i ++)
  40.     {
  41.         std::cout<<dist[i]<<" ";
  42.     }
  43.     return 0;
  44. }
  45.

畅通工程续

 畅通工程续 - HDU 1874 - Virtual Judge (vjudge.net)

思路：用dijkstra，双向建边

完整代码：

  1. #include <bits/stdc++.h>
  2. #define int long long
  3. #define PII std::pair<int,int>
  4. signed main()
  5. {
  6.     int n,m;
  7.     while(std::cin >> n >> m)
  8.     {
  9.         std::vector<std::vector<PII>>g(n+1);
  10.         std::vector<int> dist(n+1,INT_MAX);
  11.         std::vector<bool> vis(n+1);
  12.         std::priority_queue<PII,std::vector<PII>,std::greater<>> q;
  13.         for(int i = 1;i <= m;i ++)
  14.         {
  15.             int u,v,w;
  16.             std::cin >> u >> v >> w;
  17.             g[u].push_back({v,w});
  18.             g[v].push_back({u,w});
  19.         }
  20.         int s,t;
  21.         std::cin >> s >> t;
  22.         dist[s]=0;
  23.         q.push({0,s});//存dist和点数
  24.         while(!q.empty())
  25.         {
  26.             auto node = q.top();
  27.             q.pop();
  28.             int cur=node.second;
  29.             if(vis[cur]==true)
  30.                 continue;
  31.             vis[cur]=true;
  32.             for(int i = 0;i < g[cur].size();i ++)
  33.             {
  34.                 int e=g[cur][i].first;
  35.                 int w=g[cur][i].second;
  36.                 if(dist[e]>dist[cur]+w)
  37.                 {
  38.                     dist[e]=dist[cur]+w;
  39.                     q.push({dist[e],e});
  40.                 }
  41.             }
  42.         }
  43.         if(dist[t]==INT_MAX)
  44.             std::cout<<-1<<"\n";
  45.         else
  46.             std::cout<<dist[t]<<"\n";
  47.     }
  48.     return 0;
  49. }

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

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

  

闽ICP备14008679号