求最短路问题的改进算法

本文对图论中含有负权的最短路问题的算法进行了讨论 ,给出了一个具有“可节省存储空间、提高运算速度、易编程实现”等优点的改进算法 (算法三 ) ,并通过例题进一步验证了该改进算法的优越性 ,具有一定的现实意义 .     

负权最短路问题的新算法

Bellman-Ford算法自1958年以来一直是负权最短路问题的公认的最好算法之一．1970年,Yen对其进行了改进,理论上可以节省一半的计算量．本文得到了一种比Bellman-Ford算法更加优越的算法．尽管在理论上新算法无法保证完全超越于Yen的改进算法,但在许多情况下需要更少的计算量．     

Dijkstra算法的一个改进

本文得到了一种Dijkstra算法的改进算法，如果最短路问题具有n个点和m条边，那么改进算法把问题的计算复杂性从原来的O(nlogn m)降低为O(nlogn M)(M≤m)。     

带多重选择的最短路问题:复杂性和算法

本文提出了带出重选择的是短路问题,建立了该问题的数学模型,利用背包问题的一个变形问题－带限制选择的背包问题,证明了该问题是ＮＰ－Ｃ的,最后利用动态规则给出了一个伪多项式算法,其时间复杂性Ｏ（Ｃｈｍｎ）,其中ｈ是最大的选择重数。     

带点弧约束的最短路问题：复杂性和算法

本文首先提出了带点弧约束的最短路问题,证明了该问题属于ＮＰ－Ｃ,然后给出了一个伪多项式时间算法．最后给出了最小成本最短路问题的一个时间复杂性为Ｏ（ｎ２）的算法．     

基于层次分析法和最短路算法的配货模型

本文利用层次分析法,将时间、费用、客户满意度、人力资源等因素结合起来,定量给出了供货商的配货过程中每条线路的权重系数,然后结合最短路算法寻找出运送货物的最优路线．     

具有最大能量的最短路

本讨论一类新的赋权图,称为双权图,Ｇ＝（Ｖ,Ｅ;ω,ｃ）,ω称为权函数,ｃ为容量函数。并给出了Ｇ中两顶点ｕ与ｖ之间具有最大能量的最短路的算法。     

Kth最短路径的Bellman改进算法

基于对Bellm an算法的改进,得到了求解k th最短路的新算法.改进算法的优势在于从Bellm an算法只能解决最短路问题拓展到求解k th最短路问题,而且可以考虑权重为负数的情况.与传统算法相比,新算法更易于理解.     

求解运输问题的一种新算法

本文将求解分派问题的标号算法成功地用于运输问题,并证明其中的非负处理可以省略,从而把Dijk-stra算法扩展到可能出现负边权的运输问题。与通常方法比较,这种方法具有直观、简单、计算量少、及易于推广等优点;最后证明该算法是多项式的,计算复杂性仅为o(n3)(当m≤n时)。     

关于最短路问题的一个双目标优化问题

本文研究了一个双目标最短路问题的变形问题,在该变形问题中,一个目标函数还是路的长度,另一个目标函数则是路的容量,在Pareto-optimal最优解的意义下,本文给出了一个时间复杂性为O（n^3 )的算法,在字典序最优解的意义下,本文给出了一个时间复杂性为O(n^3)的算法。     

一种最短路问题的遗传算法求解

针对最短路径问题,在分析传统遗传算法不足的基础上提出了变长染色体遗传算法(ClvGA),详细论叙了其编码、基因插入(删除、变异)算子的设计,最后通过两个网络对ClvGA进行了实验仿真,结果表明:该方法在最短路径问题上表现出较好的鲁棒性.     

基于固定序的Bellman-Ford算法的改进

固定序算法是Bellman-Ford算法的一种基本改进算法。为了改变固定序算法在稀疏图上的劣势,本文通过预先订制参与迭代的点的计算顺序,对该算法进行了改进。实验表明,在稀疏图上, 改进后的算法相对于原算法计算效率提高了近50%, 并能够与国际流行的先进先出算法相媲美。本文的工作表明,固定序算法不仅在大规模稠密图上具有明显的优势,而且在稀疏图上也具有很强的竞争力。     

具有最大能量的最短路

本文讨论一类新的赋权图 ,称为双权图 ,G=( V,E;w,c) ,w称为权函数 ,c为容量函数 .并给出了 G中两顶点 u与 v之间具有最大能量的最短路的算法 .     

模糊最短路的一种算法

模糊最短路问题在许多领域有着广泛的应用,研究这一问题具有重要意义。根据多准则决策理论求非被支配路径集合,求最大效用模糊最短路以及利用模糊数排序方法求模糊最短路是常用的三种研究方法,本文利用OERI排序原理,使网络模糊边长具有线性可加性,对具有三角模糊数边权的网络给出了一种标号算法,该算法简单高效,且易于在计算机上实现,算法的时间复杂度为O(n^2)。     

点带约束成本的最短路问题

本文提出了点带约束成本的最短路问题,证明了该问题是ＮＰ－完全的,并利用动态规划给出了一个伪多项式算法,对所有顶点约束成本相同的情况,给出了一个时间复杂性为Ｏ（ｍｎ＾２）的算法,对最小点成本最短路问题,给出了一个时间复杂性为Ｏ（ｎ＾２）的算法。     

求最短路径树的一个新算法

本文考虑在一个具有ｎ个结点和ｍ条弧的网络中，求出从一个指定的结到其余所有结点的最短路径，或者找到一条具有负长度环路的问题，文中基于结点标号深度的概念，给出一个计算复杂性的界为Ｏ（ｎｍ）并且具有“尖利”（ｓｈａｒｐ）性质的求最短路径树的新算法。此外，我们还讨论了负长度环路的探测问题，并给出了一个具有“时间尖利”（ｔｉｍｅ－ｓｈａｒｐ）性质的检测负长度环路的方法。     

参数最短路的原始-对偶算法

本文利用原始－对偶方法,对于含参数λ的网络（Ｖ,Ｅ,ｆ_１-λｆ_２）,给出了某一点至其它各点的参数最短路的求解算法,其时间复杂度为 Ｏ（ｎｍ＋ｎ~２ｌｏｇｎ）．     

综合型交通分配问题的一种模型及算法

本文针对我国城市交通状况的特点,综合分析交通网络中自行车、公交车,一般机动车三种基本方式的交通流,建立了一个综合型交通分配问题的数学模型,给出了求解它的比较实用的迭代算法,推广并改进了Sheffi等的结果.