作者/EdisonZhou这是恰童鞋骚年的第篇原创文章上一篇介绍了最短路径及单源点最短路径的概念，本篇开始介绍Dijkstra算法及其代码实现。1Dijkstra算法思想
Dijkstra在对最短路径的求解方式做了大量的观察之后，首先提出了按路径长度递增产生与顶点之间的路径最短的算法，以他的名字称之为Dijkstra算法。
Dijkstra算法基本思想：
将图中顶点的集合分为两组S和U，并按最短路径长度的递增次序依次将集合U中的顶点加入到S中，在加入的过程中，总保持从原点v到S中各顶点的最短路径长度不大于从原点v到U中任何顶点的最短路径长度。Dijkstra算法采用邻接矩阵存储图的信息并计算源点到图中其余顶点的最短路径，如下图所示：
2Dijkstra算法实现代码实现
staticvoidDijkstra(int[,]cost,intv){intn=cost.GetLength(1);//计算顶点个数int[]s=newint[n];//集合Sint[]dist=newint[n];//结果集int[]path=newint[n];//路径集for(inti=0;in;i++){//初始化结果集dist=cost[v,i];//初始化路径集if(cost[v,i]0){//如果源点与顶点存在边path=v;}else{//如果源点与顶点不存在边path=-1;}}s[v]=1;//将源点加入集合Spath[v]=0;for(inti=0;in;i++){intu=0;//指示剩余顶点在dist集合中的最小值的索引号intminDis=int.MaxValue;//指示剩余顶点在dist集合中的最小值大小//01.计算dist集合中的最小值for(intj=0;jn;j++){if(s[j]==0dist[j]0dist[j]minDis){u=j;minDis=dist[j];}}s=1;//将抽出的顶点放入集合S中//02.计算源点经过顶点u到其余顶点的距离for(intj=0;jn;j++){//如果顶点不在集合S中if(s[j]==0){//加入的顶点如与其余顶点存在边，并且重新计算的值小于原值if(cost[u,j]0(dist[j]==0
dist+cost[u,j]dist[j])){//计算更小的值代替原值dist[j]=dist+cost[u,j];path[j]=u;}}}}//打印源点到各顶点的路径及距离for(inti=0;in;i++){if(s==1){Console.Write("从{0}到{1}的最短路径为：",v,i);Console.Write(v+"→");//使用递归获取指定顶点在路径上的前一顶点GetPath(path,i,v);Console.Write(i+Environment.NewLine+"SUM:");Console.WriteLine("路径长度为：{0}",dist);}}}staticvoidGetPath(int[]path,inti,intv){intk=path;if(k==v){return;}GetPath(path,k,v);Console.Write(k+"→");}
这里经历了三个步骤，第一步是构造集合U，第二步是寻找最短路径，第三步是重新计算替换原有路径。
基本测试
这里要构造的有向带权图如下图所示：
测试代码如下：staticvoidDijkstraTest(){int[,]cost=newint[5,5];//初始化邻接矩阵cost[0,1]=10;cost[0,3]=30;cost[0,4]=90;cost[1,2]=50;cost[2,4]=10;cost[3,2]=20;cost[3,4]=60;//使用Dijkstra算法计算最短路径Dijkstra(cost,0);}测试结果如下图所示：从图中可以看出，从源点0到终点4的最短路径为：0→3→2→4，该路径长度为60。3小结
本篇介绍了Dijkstra算法的基本思想及代码实现，下一篇我们会学习Floyd算法的基本思想及代码实现。
4参考资料程杰，《大话数据结构》陈广，《数据结构（C#语言描述）》段恩泽，《数据结构（C#语言版）》往期精彩回顾每天5分钟用C#学习数据结构（27）
如果本文对你有用，不妨点个“在看”或者转发朋友圈??点击阅读原文，获取文章源码
预览时标签不可点收录于话题#个上一篇下一篇