大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。
Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其它全部节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但因为它遍历计算的节点非常多,所以效率低。
Dijkstra算法是非常有代表性的最短路算法,在非常多专业课程中都作为基本内容有具体的介绍,如数据结构,图论,运筹学等等。
其基本思想是,设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。
初始时,S中仅含有源。设u是G的某一个顶点,把从源到u且中间仅仅经过S中顶点的路称为从源到u的特殊路径,并用数组dist记录当前每一个顶点所相应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u,将u加入�到S中,同一时候对数组dist作必要的改动。一旦S包括了全部V中顶点,dist就记录了从源到全部其他顶点之间的最短路径长度。
比如,对下图中的有向图,应用Dijkstra算法计算从源顶点1到其他顶点间最短路径的过程列在下表中。
eg:
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0
#include<iostream> #include<stdio.h> #include<iomanip> using namespace std; #define N 10000 #define MAX 100000099 int a[N][N]; int dist[N]; void input(int n,int m) { int p,q,len,i,j; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) a[i][j]=MAX; dist[i]=MAX; } for(i=0;i<m;i++) { cin>>p>>q>>len; if(len<a[p][q]) { a[p][q]=len; a[q][p]=len; } } } void dijkstra(int n) { int s[N],newdist,i; for(i=1;i<=n;i++) { dist[i]=a[1][i]; s[i]=0; } dist[1]=0; s[1]=1; for(i=2;i<=n;i++) { int j,tem=MAX; int u=1; for(j=2;j<=n;j++) if(!s[j]&&dist[j]<tem) { u=j; tem=dist[j]; } s[u]=1; for(j=2;j<=n;j++) { if(!s[j]&&a[u][j]<MAX) { newdist=dist[u]+a[u][j]; if(newdist<dist[j]) dist[j]=newdist; } } } } int main() { int n,m; while(scanf("%d%d",&n,&m),m||n) { input(n,m); dijkstra(n); cout<<dist[n]<<endl; } return 0; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118482.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...