共查询到20条相似文献,搜索用时 0 毫秒
1.
针对城市交通网导航的实际需要,提出了有向加权图的模型,图中顶点不仅包括路口,还包括起点和终点,并对Dijkstra算法进行改进,提出了一种基于转向限制的城市交通网最短路径算法,通过加入虚拟顶点,从而适应转向限制的条件。实验表明了该算法的正确性。 相似文献
2.
一种求解最短路径算法 总被引:2,自引:0,他引:2
在图论中,一个典型的问题就是路径问题。本文介绍一种求图的最短路径算法,该算法与[1]中的Dijkstra算法、Folyd算法相比,有较大的改进,且直观清晰,略加修改可用来求图的关键路径。 相似文献
3.
DENG Chun-yan 《数字社区&智能家居》2008,(12)
Dijkstra算法与Floyd算法是求最短路径的最常用、也是最有效的两种方法。通过从多方面对Dijkstra算法与Floyd算法的进行比较、分析,给出这两种算法的差异及Floyd关键部分的程序,并介绍了Dijkstra改进的算法。 相似文献
4.
为了提高传统最短路径算法的效率,文中在细致分析传统算法的基础上,提出了一种在业务流程中计算最短路径及寻找不合理活动环的新方法,此方法被称为最短路径的可达矩阵算法.与原有的最短路径算法相比,该方法将可达矩阵的思想引入到最短路径的计算中,可以在矩阵中显示出活动环及活动路径值.文中还详细描述了该方法所涉及的定义及运算规则.最后,将该方法应用于具体实例,并快速地找到了活动环及活动路径,为业务流程再造提供了一种新的解决方案. 相似文献
5.
6.
本文给出一种求解图最短路径问题的实用反馈式神经网络,并证明这两种网络的求解稳定性,这种网络基于最小值选择网而构成,对任意有向图和无向图均能收敛到其唯一的稳定点,由此求得图所有顶点对间的最短路径及最短路径长度,本文结果是神经网络求解非NP-骓难解类优化问题的一种新尝试。 相似文献
7.
提出一种基于Dijkstra算法的序列比对方法,该算法主要用于求最短路径,而序列比对可以转化为在有向无环图中寻找最短路径问题。对于少量序列比对,使用该算法可以求出最优解。对于多序列比对,可将在N维空间求解最短路径问题转化为在二维空间求解最短路径。该算法可以简化问题复杂度,能求得相对最优解。 相似文献
8.
顾运筠 《计算机应用与软件》2008,25(4):246-248
介绍了GIS领域最短路径搜索的一种优化模式.在Dijkstra's算法的基础上,从三个方面改进了最短路径的计算.首先引入了多级路线图,在读取线路数据时,根据路线的级别有所选择;其次,在计算最短距离时考虑速度的影响;最后,在道路的转弯处,引入虚拟路径来估算转弯对汽车行驶的影响.应用以上三种方法的实验,取得了很好的效果. 相似文献
9.
王华 《计算机与数字工程》2012,40(4):22-23,129
通过实例对比分析Dijkstra算法和Floyd算法特点及适用性,选用Dijkstra算法计算物流配送的最短路径,给出Dijkstra算法求解最短路径问题的实现方法及步骤并集成了一个小型系统,使用随机生成的数据进行最短路径求解,将生成的最短路径在随机生成的图上进行演示,并计算出两种算法执行时间,以期对物流配送中点对点的最短路径有所帮助。 相似文献
10.
11.
确定两点之间最短路径,通常要求该路径满足两点之间的权之和最小。为此采用层次遍历图的思想,设计了一种新的结构存放路径选择信息,找到一种确定这种最短路径的算法,并给出了算法描述以及实例。 相似文献
12.
13.
本文介绍的求单源点最短路径算法是基于图的搜索思想,采用了优先队列技术,符合一般人们寻找最短路径的习惯,比经典方法容易理解,运算速度也较快。 相似文献
14.
李腊元 《计算机工程与应用》1991,(1):45-49
本文讨论计算机网络最短路径算法及其实现问题。文中先论述了最短路径算法的设计思想:然后讨论了两种典型的最短路径算法:Dijkstra算法和Ford-Fulkerson算法,并给出了其实现过程。 相似文献
15.
最短路径查询是图数据管理中非常重要的一类问题.研究了基于规则的最短路径查询,它是一类特殊的最短路径查询问题.给定起点和终点,基于规则的最短路径查询是指找到一条从起点到终点的最短路径,使得此路径经过用户指定点集中的所有点,并且某些点的访问顺序满足一定的偏序规则.该问题被证明是一个NP-hard问题.目前已有的工作侧重于空间数据集(两点之间的最短距离用欧氏距离表示)上基于规则的最短路径问题,它采用穷举的方式列出所有满足规则的路径,然后选择长度最小的路径作为问题的解.然而在实际的道路交通网中,两点之间的距离等于两点之间的最短路径的长度,它往往大于两点之间的欧氏距离;此外,采用穷举的方式会造成大量重复的计算.因此,设计了一种前向搜索算法以及一些优化技术来求解该问题.最后,在不同的真实数据集上设计了大量的实验来验证算法的有效性.实验结果表明,该算法可以快速给出问题的解,而且算法的效率在很大程度上超过了现有的算法. 相似文献
16.
本文以时间代价作为目标函数,针对复杂网络的优化问题进行研究,给出了目标评价函数模型的建立过程,提出了改进的A*算法求解复杂网络中最短路径问题的算法,并以城市交通为例,对算法进行了验证,实验结果表明所提出的算法可适用于一般多重图中最短路径问题的快速求解,具有广泛的应用价值。 相似文献
17.
18.
《计算机应用与软件》2016,(11)
图在计算机领域是一种重要的数据结构,可以用来描述事物之间的复杂关系。图的节点和边具备一个或者多个不同的属性。如何结合属性对图进行聚类是目前所面临的一个新的挑战。目前的属性图聚类算法,多存在聚类效果差,消耗资源多,效率低等缺点。针对以上问题,提出一种基于最短距离的加权属性图聚类算法WASP(weighted attribute graph clustering algorithm based on shortest path),建立加权属性无向图模型,在此模型上基于最短路径算法度量节点间的关联度,以此为原则选取新的聚类中心对图进行聚类。实验表明,新的聚类算法具有更高效的聚类效果。 相似文献
19.
最短路径问题的若干算法的编程 总被引:1,自引:0,他引:1
本文讨论了带权图的最短路径问题的三类不同情况,针对每种情况介绍了较好的算法,并在MATLAB软件环境下编制了这些算法的程序。通过一个实例,验证了算法的正确性。 相似文献
20.