最短路径问题的求解

文中就最短路径问题进行了研究 ,针对具体的引例提出了六种算法 :宽度优先搜索法、A 算法、等代价搜索法、Warshall算法、动态规划法、标号法等 ,详尽分析了每种算法的内容、适用性及优缺点     

F-D算法求解最短路径

分析Floyd算法与Dijkstra算法的基本思想,将二者结合起来,给出一种新的求最短路径的优化算法——F-D算法,用F-D算法求解基于GIS的电力通信线路最短路径,并在约束条件下对所求最短路径进行修正,验证了F-D算法的先进性和高效性,优化了通信线路的拓扑,实际应用意义重大。     

在交通运输上使用动态规划求解最短路径

随着我国交通运输事业的发展,降低运输成本成为日益关注的问题。动态规划在工程技术、经济管理、工业生产、交通运输等众多领域都有广泛的应用,其中最短路径问题是动态规划在管理领域的一个重要应用。本文通过具体实例说明动态规划在交通运输方面求解最短路径的过程,方法简便,思路清晰。     

用启发式算法求解最短路径问题

提出了一种带有启发信息的邻接表结点存储结构模型,给出了结点间权值计算的具体评判函数,依据评判函数值优化邻接表中节点的相对位置.基于最短路径问题提出了带有启发信息的遗传算法思想,将启发信息加入到了初始种群生成过程中,提出了新的交叉方法.通过模拟仿真得到了算法的性能参数,并将本文算法和Dijkstra算法进行比较,结果表明...     

最短路径搜索算法在高速公路收费系统中的应用

如何快速建立、维护可靠的各站点间的费用矩阵是高速公路联网收费系统的关键．根据重庆高速公路路网的特点，采用分治法，提出了一种将Floyd算法和Johnson算法相结合的改进算法来求任意2结点间的最小费用矩阵的算法，并对算法复杂度进行了分析．     

一种实用的最短路径求解算法

本文从地图上城市交通网络中道路路段间的地理关联关系入手,探讨了一种求两节点间最短径的新算法,在地理信息系统软件ＭａｐＩｎｆｏ中编程实并取得良好的效果。该算法的时间花费极少,有极强的实用性,并有继续研究的价值。     

Groebner基理论在最短路径问题中的应用

在最短路径问题中，若连通图中相邻节点对xi和xj间的路径径为aij，则节点之间的关系可用多项式xi-xj-aij描述，把所有的这种多项式以终点所表示的项为首项归纳和排序得到集 F，若存在最短路径供选择，则F生成理想的Groebner基为{1}，因此，求节点xm则xk的最短路径，可用多项式xk-xm对F中的无素约化，所得到的一个常数就是这条可达路径的长度；若有多条路径可供选择，则每条路径对应一个常数，所有些常数中的最小数就是最短路径的长度。     

求解最短路径问题的DNA动态规划算法

最短路径问题是一个组合优化问题,许多交通运输、工程、管理等实际问题可转化为最短路径问题进行求解。文中利用DNA计算的并行计算模式,给出一个求解最短路径问题的DNA动态规划算法,该算法最多需要7n-11个生物操作。     

三维最短路径算法在山间修路问题中的应用

针对交通工程中山间修路问题,建立了三维最短路径模型,并将三维最短路径问题转化为图论最短路径问题,提出了一种三维最短路径算法。结果表明,三维最短路径算法可有效地解决山间修路中出现的问题。     

最短路径搜索算法在高速公路收费系统中的应用

如何快速建立、维护可靠的各站点间的费用矩阵是高速公路联网收费系统的关键.根据重庆高速公路路网的特点,采用分治法,提出了一种将Floyd算法和Johnson算法相结合的改进算法来求任意2结点间的最小费用矩阵的算法,并对算法复杂度进行了分析.     

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

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

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

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

A genetic algorithm for the pareto optimal solution set of multi-objective shortest path problem

Unlike the shortest path problem that has only one optimal solution and can be solved in polynomial time, the muhi-objective shortest path problem （ MSPP ） has a set of pareto optimal solutions and cannot be solved in polynomial time. The present algorithms focused mainly on how to obtain a precisely pareto optimal solution for MSPP resulting in a long time to obtain multiple pareto optimal solutions with them. In order to obtain a set of satisfied solutions for MSPP in reasonable time to meet the demand of a decision maker, a genetic algo- rithm MSPP-GA is presented to solve the MSPP with typically competing objectives, cost and time, in this pa- per. The encoding of the solution and the operators such as crossover, mutation and selection are developed. The algorithm introduced pareto domination tournament and sharing based selection operator, which can not only directly search the pareto optimal frontier but also maintain the diversity of populations in the process of evolutionary computation. Experimental results show that MSPP-GA can obtain most efficient solutions distributed all along the pareto frontier in less time than an exact algorithm. The algorithm proposed in this paper provides a new and effective method of how to obtain the set of pareto optimal solutions for other multiple objective optimization problems in a short time.     

A*算法改进及其在动态最短路径问题中的应用

动态最短路径搜索算法是智能交通系统技术应用的关键问题之一．为了解决这一问题,提出以一致性原则动态形式为基础的动态A*算法(dynamic A* algorithm,DA* algorithm)并证明了在两节点间动态下界满足一致性原则动态形式前提下,该算法能够求解满足先进先出原则的动态网络中两节点间最短路径问题．在以广州市交通路网为基础的动态网络上对DA*算法进行试验．试验结果表明,Dijkstra算法的和A*算法的平均计算时间分别是DA*算法的6．55和1．43倍．     

浅析城市道路网中的最短路径算法

论文主要分析了一些经典的最短路径算法,以及这些最短路径算法单独应用于城市道路网中存在的局限性。在此基础上提出了一种改进的Dijkstra算法用来解决城市道路网中的最短路径问题,并给出了改进后的算法优于传统算法的优势之处。     

有向最短路的“原始-对偶”算法

给出了利用 互补松弛原理 以及 原始-对偶原理 ,在一个有向图D=（V,A,ω）中寻找顶点s到顶点t最短路的算法和过程。