鱼C论坛

 找回密码
 立即注册
查看: 531|回复: 4

最短路径求解算法的实现和时间复杂度分析

[复制链接]
最佳答案
0 
发表于 2019-12-6 13:55:46 | 显示全部楼层 |阅读模式
10鱼币
大佬们,请帮帮忙,可额外支付宝转账,留言qq私聊

WX20191206-135305@2x.png
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2019-12-7 12:08:21 | 显示全部楼层
根本看不懂   
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
 楼主| 发表于 2019-12-7 20:05:40 | 显示全部楼层

太难了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
0 
发表于 2020-1-11 23:14:46 | 显示全部楼层
本帖最后由 月亮会发光 于 2020-1-11 23:16 编辑

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
2 
发表于 2020-1-11 23:19:34 | 显示全部楼层
  1. /*
  2. 由于本人没学Floyd就介绍 Dijkstra和SPFA
  3. 代码为c++

  4. 第一段代码用的是spfa算法,相对来说时间复杂度更高一些
  5. 如果图随机生成,时间复杂度为O(KM) (常数k想小一点小就看你自己怎么优化了)
  6. 但是实际上SPFA的算法复杂度是O(NM)。
  7. 不怎么推荐这个算法,比如2018年NOi比赛就卡了SPFA时间复杂度
  8. (K可以当作常数,m边数,n点数)
  9. */
  10. #include <iostream>
  11. #include <cstdio>
  12. #include <queue>
  13. #define MAXN 10010
  14. #define MAXM 500010
  15. #define INF 2147483647
  16. using namespace std;

  17. queue<int> q;
  18. struct Edge {
  19.         int next,to,w;
  20. }edge[MAXM];
  21. int n,m,s,cnt,head[MAXN],vis[MAXN],dis[MAXN];

  22. void spfa() {
  23.         for(int i=1;i<=n;i++)
  24.                 dis[i] = INF;
  25.         q.push(s);
  26.         dis[s] = 0;
  27.         vis[s] = 1;
  28.         while(!q.empty()) {
  29.                 int u = q.front();
  30.                 q.pop();
  31.                 vis[u] = 0;
  32.                 for(int i=head[u];i;i=edge[i].next) {
  33.                         int v = edge[i].to;
  34.                         if(dis[v]>dis[u]+edge[i].w) {
  35.                                 dis[v] = dis[u] + edge[i].w;
  36.                                 if(!vis[v]) {
  37.                                         vis[v] = 1;
  38.                                         q.push(v);
  39.                                 }
  40.                         }
  41.                 }
  42.         }
  43. }
  44. void edge_add(int u,int v,int w) {
  45.         cnt++;
  46.         edge[cnt].next = head[u];
  47.         edge[cnt].to = v;
  48.         edge[cnt].w = w;
  49.         head[u] = cnt;
  50. }

  51. int main() {
  52.         cin >> n >> m >> s;
  53.         for (int i=1;i<=m;i++) {
  54.                 int u,v,w;
  55.                 cin >> u >> v >> w;
  56.                 edge_add(u,v,w);
  57.         }
  58.         spfa();
  59.         for(int i=1;i<=n;i++)
  60.                 cout << dis[i] << " ";
  61.         return 0;
  62. }





  63. /*下面这段代码是Dijkstra
  64. 采用了优先队列priority_queue+重载的堆优化
  65. priority_queue是c++ stl库里的东西,可以学习下

  66. 时间按复杂度O( (n+m) log n)
  67. m很大的时候会比较慢
  68. 不过总的来说比SPFA优化了许多
  69. */
  70. #include <iostream>
  71. #include <cstdio>
  72. #include <queue>
  73. #define MAXN 100100
  74. #define MAXM 5000100
  75. #define INF 2147483647
  76. using namespace std;


  77. struct Edge {
  78.         int next,to,w;
  79. }edge[MAXM];
  80. int n,m,s,cnt,head[MAXN],vis[MAXN],dis[MAXN];

  81. struct node {
  82.         int pos,dis;
  83.         bool operator<(const node &a) const{
  84.                 return a.dis<dis;
  85.         }
  86. };
  87. priority_queue<node> q;

  88. void dj() {
  89.         for(int i=1;i<=n;i++)
  90.                 dis[i] = INF;
  91.         dis[s] = 0;
  92.         node tmp;
  93.         tmp.pos = s;
  94.         tmp.dis = 0;
  95.         q.push(tmp);
  96.         while(!q.empty()) {
  97.                 int u = q.top().pos;
  98.                 q.pop();
  99.                 if(!vis[u]) {
  100.                         vis[u] = 1;
  101.                         for(int i=head[u];i;i=edge[i].next) {
  102.                                 int v = edge[i].to;
  103.                                 if(dis[v]>dis[u]+edge[i].w) {
  104.                                         dis[v] = dis[u] + edge[i].w;
  105.                                         tmp.pos = v;
  106.                                         tmp.dis = dis[v];
  107.                                         q.push(tmp);
  108.                                 }
  109.                         }
  110.                 }
  111.         }
  112. }
  113. void edge_add(int u,int v,int w) {
  114.         cnt++;
  115.         edge[cnt].next = head[u];
  116.         edge[cnt].to = v;
  117.         edge[cnt].w = w;
  118.         head[u] = cnt;
  119. }

  120. int main() {
  121.         cin >> n >> m >> s;
  122.         for (int i=1;i<=m;i++) {
  123.                 int u,v,w;
  124.                 cin >> u >> v >> w;
  125.                 edge_add(u,v,w);
  126.         }
  127.         dj();
  128.         for(int i=1;i<=n;i++)
  129.                 cout << dis[i] << " ";
  130.         return 0;
  131. }
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1

GMT+8, 2020-8-9 04:33

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表