7-2 迪杰斯特拉方法实现最短路径
2021/12/8 23:48:37
本文主要是介绍7-2 迪杰斯特拉方法实现最短路径,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
用迪杰斯特拉算法实现有向网的最短路径
输入格式:
第一行输入有向网的顶点和边数,第二行输入各顶点值,用空格间隔,第三行开始输入各条边的 两个点的及边上的权值,用空格间隔。最后一行输入要求路径的两个顶点。
输出格式:
输出最短路径经过的各顶点,中间用-->连接。
输入样例:
在这里给出一组输入。例如:
6 8 0 1 2 3 4 5 0 2 10 0 4 30 0 5 100 1 2 5 2 3 50 3 5 10 4 3 20 4 5 60 0 3结尾无空行
输出样例:
在这里给出相应的输出。例如:
0-->4-->3结尾无空行 代码:
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int N=1010; struct edge{ int v,w; edge* next; }; struct node{ int k; edge* next; }a[1010]; int n; int find(int u){ for(int i=0;i<n;i++){ if(a[i].k==u){ return i; } } return -1; } void add(int u,int v,int w){ edge* e=new edge(); e->v=v; e->w=w; e->next=a[u].next; a[u].next=e; } int dis[N],pre[N]; bool st[N]; void dijkstra(int u){ memset(pre,-1,sizeof pre); memset(dis,0x3f,sizeof dis); dis[u]=0; for(int i=0;i<n-1;i++){ int k=-1; for(int j=0;j<n;j++){ if(st[j]==0&&(k==-1||dis[j]<dis[k])){ k=j; } } if(dis[k]==0x3f3f3f3f){ continue; } st[k]=1; for(edge* j=a[k].next;j!=NULL;j=j->next){ int v=j->v,w=j->w; if(dis[v]>dis[k]+w){ dis[v]=dis[k]+w; pre[v]=k; } } } } void showRoad(int v){ if(pre[v]!=-1){ showRoad(pre[v]); cout<<"-->"<<a[v].k; }else{ cout<<a[v].k; } } int main(){ int m; cin>>n>>m; for(int i=0;i<n;i++){ int k; cin>>k; a[i].k=k; } for(int i=0;i<m;i++){ int u,v,w; cin>>u>>v>>w; int uu=find(u),vv=find(v); add(uu,vv,w); } int u,v; cin>>u>>v; dijkstra(u); showRoad(v); return 0; }
这篇关于7-2 迪杰斯特拉方法实现最短路径的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)