Dijkstra算法 最短路径
2022/2/5 20:15:14
本文主要是介绍Dijkstra算法 最短路径,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1 #include <bits/stdc++.h> 2 const int INF=99999; 3 using namespace std; 4 int n,m,u; 5 int dis[10000]; 6 int dist[10000][10000]; 7 int vis[10000]; 8 int main() 9 { 10 cin>>n>>m; 11 int a,b,c; 12 for(int i=1;i<=n;i++) 13 { 14 for(int j=1;j<=n;j++) 15 { 16 if(i==j) dist[i][j]=0; 17 else 18 { 19 dist[i][j]=INF; 20 } 21 } 22 } 23 memset(vis,0,sizeof(vis)); 24 vis[1]=1; 25 26 27 for(int j=1;j<=m;j++) 28 { 29 cin>>a>>b>>c; 30 dist[a][b]=c; 31 } 32 33 for(int i=1;i<=n;i++) 34 { 35 dis[i]=dist[1][i]; 36 } 37 for(int i=1;i<=n-1;i++) //类似于找相近的点相连 38 { 39 int minn=INF; 40 for(int j=1;j<=n;j++) 41 { 42 if(vis[j]==0&&dis[j]<minn) 43 { 44 minn=dis[j]; 45 u=j; 46 } 47 } 48 vis[u]=1; 49 for(int v=1;v<=n;v++) //此处判断两条路那一条更近一点 松弛 50 { 51 if(dist[u][v] < INF) 52 { 53 if(dis[v] > dis[u] + dist[u][v]) 54 dis[v] = dis[u] + dist[u][v]; 55 } 56 57 } 58 } 59 for(int i=1;i<=n;i++) 60 { 61 cout<<dis[i]<<' '; 62 } 63 }
这篇关于Dijkstra算法 最短路径的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性