Dijkstra算法
Dijkstra算法算是贪心思想实现的，首先把起点到所有点的距离存下来找个最短的，然后松弛一次再找出最短的，所谓的松弛操作就是，遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近，如果更近了就更新距离，这样把所有的点找遍之后就存下了起点到其他所有点的最短距离。
问题引入：
指定一个点（源点）到其余各个顶点的最短路径，也叫做“单源最短路径”。例如求下图中的1号顶点到2、3、4、5、6号顶点的最短路径。
下面我们来模拟一下：
这就是Dijkstra算法的基本思路：
接下来是代码：
已经把几个过程都封装成了基本模块：
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #define Inf 0x3f3f3f3f using namespace std; int map[1005][1005]; int vis[1005],dis[1005]; int n,m;//n个点，m条边 void Init () { memset(map,Inf,sizeof(map)); for(int i=1;i<=n;i++) { map[i][i]=0; } } void Getmap() { int u,v,w; for(int t=1;t<=m;t++) { scanf("%d%d%d",&u,&v,&w); if(map[u][v]>w) { map[u][v]=w; map[v][u]=w; } } } void Dijkstra(int u) { memset(vis,0,sizeof(vis)); for(int t=1;t<=n;t++) { dis[t]=map[u][t]; } vis[u]=1; for(int t=1;t<n;t++) { int minn=Inf,temp; for(int i=1;i<=n;i++) { if(!vis[i]&&dis[i]<minn) { minn=dis[i]; temp=i; } } vis[temp]=1; for(int i=1;i<=n;i++) { if(map[temp][i]+dis[temp]<dis[i]) { dis[i]=map[temp][i]+dis[temp]; } } } } int main() { scanf("%d%d",&m,&n); Init(); Getmap(); Dijkstra(n); printf("%d\n",dis[1]); return 0; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/bian-cheng-ji-chu/103343.html