Dijkstra及基于Dijkstra的前N条最短路径算法在智能交通系统中的应用

介绍了D ijkstra算法在智能交通系统的套牌车查询子系统中的应用;分析指出了文献[1]中算法存在的问题;通过对此算法的改进,完善了基于D ijkstra算法的前N条最短路径算法。通过实验及实际应用对改进后的算法进行了验证。

前N条最短路径问题的算法及应用

现有最短路径问题指的是狭义最短路径问题 ,针对该问题而设计的算法只能求得最短的一条路径 .前 N条最短路径拓宽了最短路径问题的内涵 (即不仅要求得最短路径 ,还要求得次短、再次短…第 N短路径 ) ,是广义最短路径问题 .在图论理论基础上分析问题之后 ,设计了一个递归调用 Dijkstra算法的新算法 ,该算法可以求取前 N条最短路径 ,而且时间、空间复杂度都为多项式阶 .该算法已经成功应用于一个交通咨询系统中 ,自然满足实时应用需要 .

基于N条最短路径的成品油管道优化设计

采用了赋权有向图来表示成品油管道工艺方案优化设计问题,若干个泵站位置候选点对应图的顶点,两顶点间管段的总费用现值对应弧的权值,通过循环调用Dijkstra算法,求解出了前N条最短路径作为最优和次优方案,以备多方案比选。该方法既兼顾了工程实际的要求,又可以给出最优、次优工艺方案。实际算例表明该方法切实可行。所提出的方法可以推广应用到其它油气管道工艺方案优化设计或其它工程应用。

一种改进的求解前N条最短路径问题的多重标号算法

求前N条最短路径问题是一个在实际工程中有着广泛应用背景的重要问题.针对传统问题描述中存在的局限,对该问题的定义进行了扩展,从而使此问题的求解更为完备.介绍了求解传统N最短路径问题的多重标号算法的基本思想,分析了其存在的问题,提出了相应的针对扩展N最短路径问题的改进算法.在详细描述算法实现的基础上,对改进算法的时间和空间复杂度进行了理论分析,并分别与理论严密算法中的候选删除边算法和有损算法中的遗传算法进行了对比实验.结果表明,本文算法能以更好的时间性能正确地求解得到全局最优路径集.

前N条最短路径在网络中的应用

在Dijkstra算法基础上,提出基于双向搜索的前N条最短路径算法,给出了相应的数据结构和算法实现,同时针对网络的动态性,对静态算法作了适当的改进。