本篇内容主要讲解“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<G.numV; i++) { ShortPath[i] = G.arr[pos][i]; final[i] = false; PathArc[i] = 0; } ShortPath[pos] = 0; //该点到自身距离 final[pos] = true; //将该店纳入 final 集合中 //开始主循环每次求的pos这点要某个顶点的最短路径 int k=0; for(int v=1;v<G.numV; v++) { int min = 65535; for(int w=0;w<G.numV;w++) { if(!final(w) && ShortPath[w]<min) {//不是到本身的最短的一个点的距离,类似普里姆法 min = ShortPath[w]; k = w; } } final[k] = true ;//将该点纳入final数组中 for(int j=0;j<G.numV;j++) { if(!final[j] && (min+G.arr[k][j])<ShortPath[j]) { ShortPath[j] = min+G.arr[k][j]; PathArc[j] = k; } } } }
比如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算法举例分析”有了更深的了解,不妨来实际操作一番吧!这里是亿速云网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。