Dijkstra算法地铁站台出口路径的选择研究(5)
时间:2018-05-08 10:31 来源:毕业论文 作者:毕业论文 点击:次
2.3 Dijkstra算法 2.3.1 概念 Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 2.3.2 原理 首先，引进一个辅助向量D，它的每个分量D[i]表示当前所找到的从始点v到每个终点vi的的长度：如D[3]=2表示从始点v到终点3的路径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于长度。它的初始状态为：若从v到vi有弧，则D为弧上的权值；否则置D为∞。显然，长度为 D[j]=Min{D | vi∈V} 的路径就是从v出发的长度最短的一条。此路径为(v,vj)。 那么，下一条长度次短的是哪一条呢？假设该次短路径的终点是vk，则可想而知，这条路径或者是(v,vk)，或者是(v,vj,vk)。它的长度或者是从v到vk的弧上的权值，或者是D[j]和从vj到vk的弧上的权值之和。 一般情况下，假设S为已求得的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧(v,x)，或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的的长度必是D[j]=Min{D | vi∈V-S} 其中，D或者是弧(v,vi)上的权值，或者是D[k](vk∈S)和弧(vk,vi)上的权值之和。 2.3.3 算法思想 按路径长度递增次序产生算法： 把顶点集合V分成两组：一组是S：已求出的顶点的集合（初始时只含有源点V0），另一组为V-S=T：尚未确定的顶点集合 将T中顶点按递增的次序加入到S中，保证从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度以及每个顶点都对应一个距离值。S中顶点对应的是从V0到此顶点的长度，T中顶点对应的是从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度。 （反证法可证） 求最短路径步骤 算法步骤如下： 1. 初始时令 S={V0},T={其余顶点}，T中顶点对应的距离值 若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值 若不存在<V0,Vi>，d(V0,Vi)为∞ 2. 从T中选取一个其距离值为最小的顶点W且不在S中，加入S 3. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值 重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止 3 系统设计 本课题是地铁站台最短路径选择，主要需要解决的是最短路径的问题，然后在解决最短路径的前提下，需要针对地铁站台作出相应的设计和应用。 地铁与我们的生活是息息相关的，是我们日常生活中必不可少的交通工具，由于地铁准时、高效，现在很多人们的出行都会选择地铁。对于初次到的一个陌生的站台，想要找自动扶梯、电梯或者是需要达到的出口都是件很困难的事。所以对于地铁站台最短路径的选择首要的是要对地铁站台有清楚的认识和了解，知道地铁站台内的基本路线和设施。 查找了相关资料，对地铁站台有初步的认识和了解，知道地铁站内的基本路线和设施。之后进行实地考察，对地铁站内自动扶梯、楼梯、升降电梯、残疾人通道、安全出口进行统计分析，并收集地铁站高峰和非高峰时段的人流情况、站台情况和出口情况。 3.1 本课题的重点和难点 3.1.1 本课题的重点 通过调研结果对站台、站厅情况进行分析，获得各电梯、扶梯、楼梯的位置以及出口位置，设置可以通行的路线，在正常、特殊以及故障或突发情况下提供最短路径。 (责任编辑：qin) |