最短路问题在运输网络中的应用

最短路问题是在图的基础上衍生出来的,也是网络优化中的一个基本问题,许多选择优化问题都可以转化为最短路问题来求解。本文重在研究公路网络运输中的最短路问题。     

最短路问题的灵敏度分析与最短路调整

本文讨论的是无负回路的有向网络,在己知网络各节点间最短路的前提下,当网络中的个别节点、权值、弧发生变化时,变化对最短路有无影响,若有,如何利用变化前的最短路得到改变后的最短路,即:利用网络的独特优势,建立最短路问题的灵敏度分析算法.     

关于动态最短路问题的探讨

主要研究网络优化领域中一种具有动态特征的最短路问题,给出了离散时间模型下关于时间和费用的动态最短路问题的描述,通过引入时间扩张图概念,将动态最短路问题转化为对应的静态网络中的最短路问题,讨论了两类动态最短路问题的复杂性并给出算法。     

含有禁止路线网络中的最短路问题

给出了求解含有禁止路线网络中的最短路问题的一个算法 .     

用摹矩阵寻求网络的最短路

应用了半城、摹矩阵和优选半域等概念,把摹矩阵的计算运用到图论中的寻求负权网络中的最短路以及寻求网络中各点间的最短路问题上。实例的计算结果表明,这是一种计算简便,行之有效的方法.     

哈明距离下的最短路反问题

反优化问题是指修改给定的参数,使得优化问题的最优解的目标函数值满足一定的约束。本文中我们考虑的是哈明距离下的最短路反问题:通过修改给定网络上弧的长度,使得修改后网络中指定点之间的最短路长度不超过给定的常数,而其中修改费用是用哈明距离来衡量的,我们证明了哈明距离下的最短路反问题是强NP-完全的。     

赋有权向量网络的字典序最短路

本文以多目标优化设计为背景,提出了赋有权向量网络的字典序最短路概念。在字典序极小的意义下,推广了最短路问题的Dijkstra算法和Floyd算法,讨论了算法的复杂性,为一类问题的多目标优化决策提供了一种工具。     

带负权最短路问题前趋法的改进

针对在带负权的有向网络中求最短路的前趋法的不足,结合动态规划思想从提高算法效率方面对其进行了改进,并提出了一种新算法.新算法通过引入变量记录当前节点到宿节点的最短路权,避免了前趋法中比较多条前趋路时反复计算最短路的冗余运算,同时弥补了动态规划不能直接求解带回路的有向网络最短路的缺陷,是一种计算带负权最短路问题的简便方法.该算法对非负权网络中的最短路问题同样有效.最后仿真结果和算例表明了新算法的有效性.     

用Excel求解拓扑网规划问题的研究

用Excel提供的“规划求解”功能解决网络规划问题中的主要问题：最大流问题、最小代价流问题、最短路问题和网络计划关键路径问题．     

哈明距离下的最短路反问题

反优化问题是指修改给定的参数，使得优化问题的最优解的目标函数值满足一定的约束。本文中我们考虑的是哈明距离下的最短路反问题：通过修改给定网络上弧的长度，使得修改后网络中指定点之间的最短路长度不超过给定的常数，而其中修改费用是用哈明距离来衡量的，我们证明了哈明距离下的最短路反问题是强NP-完全的。     

最短路问题的通用算法--最短初等链法

最短初等链法是求解网络图最短路问题的通用算法，它突破了以往诸算法的局限性，适用范围广，具有广阔应用前景。     

基于网络限制的最短路模型

带限制的网络是一类特殊的网络,如具有禁止通行限制信息的交通路网.由于此类网络的最短路径的求解是有后效性的,因此经典的Dijkstra算法等就无法用来解决此类问题.提出了一种路网带限制的交通网络最短路径建模方法.该方法将具有禁行限制的特殊网络转化成一个一般的网络模型,从而可用任一传统高效的算法完成对其最短路径的求解.     

赋权多阶段有向图最短路的求法

多阶段有向图是常见的一种有向图,许多运输、工程、管理等实际问题能转化为有向图最短路问题进行求解,尤其赋权多阶段有向图对解决该类实际问题更具有重要意义.研究了赋权多阶段有向图的最短路问题,从图上逆序标号法、表上作业法和动态规划法不同的角度对文中实例给出了赋权多阶段有向图最短路求解方法。     

随机网络的动态最短路研究

本文对于权值为时间t的连续函数动态最短路的问题,通过先求解某个时刻从起点到终点的最短路,然后分析某个时刻的最短路与该时刻的邻域内的最短路关系,再借助有限覆盖定理,求解出某一闭时间区间内的最短路时．从一新途径研究了变权的最短路问题．     

路网车流径路优化调整中的最短径路算法

目前铁路车流径路基本上都是按照路网的最短路径来安排的,首先一般都采用Dijkstra算法计算最短路径,然后参考相应区段的能力限制,对车流进行分配,对车流量超过能力的区段重新进行车流调整,这时需要重新计算新条件下两点间最短路径,一般仍采用Dijkstra算法重新计算两点最短路径,这大大地浪费了前期的计算最短路径的信息,增加了计算工作量,本文采用A*算法作为一种启发式算法,可以克服这一缺陷。     

大规模网络最短路径算法的优化及实现

求解大规模复杂网络的最短路径问题由于其计算速度慢、需耗费的存储空间大,是与地理信息相关的应用系统经常遇到的瓶颈问题．在深入分析各种常用最短路径算法基础上,基于经典Dijkstra算法,从时间和空间优化角度,实现一种计算任意2点间最短路径的优化算法．初步实验表明,优化后的算法在处理大规模复杂网络的最短路径问题时比经典Dijkstra算法在计算时间上缩短了80％,在耗费的存储空间上减少了将近一倍．     

A shortest path algorithm for moving objects in spatial network databases

One of the most important kinds of queries in Spatial Network Databases （SNDB） to support location-based services （LBS） is the shortest path query. Given an object in a network, e.g. a location of a car on a road network, and a set of objects of interests, e.g. hotels, gas station, and car, the shortest path query returns the shortest path from the query object to interested objects. The studies of shortest path query have two kinds of ways, online processing and preprocessing. The studies of preprocessing suppose that the interest objects are static. This paper proposes a shortest path algorithm with a set of index structures to support the situation of moving objects. This algorithm can transform a dynamic problem to a static problem. In this paper we focus on road networks. However, our algorithms do not use any domain specific information, and therefore can be applied to any network, This algorithm＇s complexity is O（klog2i）, and traditional Diikstra＇s comolexitv is O（（i ＋ k）^2）.