一种基于Dijkstra最短路径算法的改进算法

Dijkstra算法是求解最短路径的经典算法,是在许多应用中解决最短路径问题的理论基础,但实际应用中涉及的许多限制条件要求人们必须对该算法进行改进和优化.在分析经典Dijkstra算法思想的基础上,给出Dijkstra算法的一种改进算法.在该算法中图的存储表示采用邻接表的方式,避免邻接矩阵在工程应用中的局限性.在最短路径的计算过程中,采用优先级队列与反向N叉树相结合的方式,以便通过实现可降级的优先队列来改进Dijkstra算法.给出了改进形Dijkstra算法的方法和流程,分析了其算法复杂度,并对改进后的算法进了详细的分析和测试.

基于对策理论的交通流分配新方法

建立基于对策理论的交通流分配模型,并以实例阐述其具体应用方法。本方法由于在分配中考虑了路网状况,因而其分配结果更加符合实际,且能实现全有全无分配与多路径分配的统一。

基于云计算的蚁群算法求解城市路网最短路径

为了解决在求解城市路网最短路径时遇到的数据量大的问题,提出了基于云计算的蚁群算法。该算法结合了模拟退火算法,在弥补蚁群算法缺点的同时,与MPI并行蚁群算法相比,随着节点数的增加运行速度明显加快。

城市交通时间最短路径计算模型及应用仿真

研究道路状态信息和路口固定延迟模型优化问题,城市交通时间最短路径(T'DSP)是统计意义上的最优路径,对个体车辆而言并非最优,主要原因在于没有考虑车辆通行与交通信号的时空相位关系。通过对上述关系的研究,提出了基于交通信号的路口延迟和时间最短路径(TLBSP)的计算模型及改进Dijkstra算法,适用于现有主要交通网络和交通规则,能实现交通信号控制下各车最短时间路径的计算。实验结果表明,TLBSP算法的时间最短路径优于距离最短路径算法和固定延时的TDSP算法,改进算法可应用于城市交通导航,能促使车辆在空间上合理分布,有利于缓解城市交通拥堵。

IP组播路由结构的性能分析

目前因特网协议（ＩＰ）组播路由协议在结构上可分为基于源和基于组的两类转发树结构．把这两种组播路由结构在扩展性能、对单播路由算法的依赖性、业务量拥塞特性、网络的额外开支量以及对源ＩＰ地址的依赖性等方面进行分析比较，指出它们在不同应用场合的优缺点，为两种结构的路由协议相互结合。

基于加权节点的Steiner树启发式算法

Steiner最小树问题是一个NP完全问题,被广泛应用在通信网络中点到多点的路由选择。为了实现更多链路的共享,减少所求Steiner树的费用,提出了一种基于加权节点求解Steiner树的启发式(NWMPH)算法。该算法构造了非正则点的权值公式,给每一个非正则点赋权值,根据权值对链路的费用进行修正,通过修正费用最短路径依次把所有的正则点连接起来,得到包含所有正则点的最小树。对STEINLIB标准数据集中的部分数据进行计算,结果表明:NWMPH算法与MPH算法所用时间基本相同,得到的Steiner树费用优于MPH算法;NWMPH算法比KBMPH算法所用时间少,得到的Steiner树费用绝大多数优于KBMPH算法。

Dijkstra算法在三亚旅游线路规划中的应用

建立数学模型,结合数据库技术,运用Dijkstra算法,计算出任意两个景点之间的最低费用、最短时间、最短路程,供游客路线选择和相关管理者规划旅游线路时参考.

线路设计中多方案组合优化算法

为了使设计者从道路线路设计的繁重计算统计工作中解脱出来,在研究了局部方案间内在关联的基础上,提出了将局部方案分解为更小单位的逻辑方案,用有向网络图表示逻辑方案间的拓扑关系,采用节点-弧段联合数据结构来表示网络图;同时基于最短路径理论,提出了在网络图中智能化搜索综合指标最优的逻辑方案集,自动形成整体方案的组合优化算法。研究结果表明:该组合优化算法是正确的,应用该算法能自动生成整体最优的方案,提高了设计效率和水平。