Dijkstra算法举例分析

本篇内容主要讲解"Dijkstra算法举例分析"，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习"Dijkstra算法举例分析"吧!

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
最短路径？其实就是字面意思，一个带边值的图中从某一个顶点到另外一个顶点的最短路径。
官方定义：对于内网图而言，最短路径是指两顶点之间经过的边上权值之和最小的路径。
并且我们称路径上的第一个顶点为源点，最后一个顶点为终点。
由于非内网图没有边上的权值，所谓的最短路径其实是指两顶点之间经过的边数最少的路径。

它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。

迪杰斯特拉算法时间复杂度为 0(n^2)；

算法在实现步骤上类似与 普利姆算法 从最原始顶点开始 一步一步求到所有顶点的最小距离；

但是如果我们要寻找另外一个点到所有点的距离最小值 就要重新运行一遍这个算法

#define maxV 9 //最大顶点数  #define min 65535;  void DJSTL(MGraph G， int pos) //pos 这点到其余个点距离最小值  {      bool final[maxV];//判断是否已经存到S集合中      int ShortPath[maxV];//一个点到其余点的距离 存储的是长度      int PathArc[maxV];// 存储最短路径下标      for(int i = 0; i
比如pos=0时求的 ShortPath{0，1，4，7，5，8，10，12，16}他表示V0 这个点到各个顶点的最短路径数。比如V0->V8 = 16 V0->V7=12;
PathArc{0,0,1,4,2,4,3,6,7}
PathArc[8]=7 表示V0->V8 终点V8的前驱顶点是V7
PathArc[7]=6 表示V7前驱顶点是V6
PathArc[6]=3 表示V6前驱顶点是V3
PathArc[3]=4 表示V3前驱顶点是V4
PathArc[4]=2 表示V4前驱顶点是V2
PathArc[2]=1 表示V2前驱顶点是V1
PathArc[1]=0 表示V1前驱顶点是V0
最短路径为V0->V1->V2->V4->V3->V6->V7->V8
到此，相信大家对"Dijkstra算法举例分析"有了更深的了解，不妨来实际操作一番吧！这里是网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！