【精选】数据结构第七次作业·第四题·北京地铁线路查询&Dijkstra算法 |
您所在的位置:网站首页 › g8127经过的站点 › 【精选】数据结构第七次作业·第四题·北京地铁线路查询&Dijkstra算法 |
一.Dikjstra算法:
(部分内容出自博客Dijkstra算法(迪杰斯特拉算法)_持之以恒2016-CSDN博客) 基本思想:Dikjstra算法采用广度优先策略,从起始点v0开始,层层向外拓展。正是如此,导致其搜索成功率较高但是时间复杂度较大为O(n²)。 将顶点划分为两种:集合S:已经确定最短路径的顶点;集合U:没有确定最短路径的顶点。 操作步骤1.初始:从s开始,S中只有元素S,其他元素都在U中。且U中顶点与s的距离定义为:若U,s直接连接,则其距离就为其邻接矩阵定义的距离。若U,s不直接连接,则其距离为无穷大(INF)。这样定义是因为可以优先考虑与D相邻的顶点,实现BFS。 2.从U中选出距离最小的顶点k,并把k加入到S中。且k的前序就是v0。 3.更新距离:以k为依托,与k直接连接的顶点到v0的距离(但不一定最小)就等于其到k的距离加上k到v0的距离。若这个距离小于当前记录的距离,则这个顶点的前序就是k。 4.重复2,3到遍历结束。 图解示例----- S是已计算出最短路径的顶点的集合 ----- U是未计算出最短路径的顶点的集合 ----- C(3)表示顶点C到起点D的最短距离为3 选择顶点D S={D(0)} U={A(∞), B(∞), C(3), E(4), F(∞), G(∞)} 选取顶点C S={D(0), C(3)} U={A(∞), B(13), E(4), F(9), G(∞)} 选取顶点E S={D(0), C(3), E(4)} U={A(∞), B(13), F(6), G(12)} 选取顶点F S={D(0), C(3), E(4), F(6)} U={A(22), B(13), G(12)} 选取顶点G S={D(0), C(3), E(4), F(6), G(12)} U={A(22), B(13)} 选取顶点B S={D(0), C(3), E(4), F(6), G(12), B(13)} U={A(22)} 选取顶点A S={D(0), C(3), E(4), F(6), G(12), B(13), A(22)} U={} 代码如下: void Dijkstra(int v0){ int minweight,minv; int wfound[MAXVEX]={0};//to sign if the shortest path from i to v0 is found for(int i=0;i |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |