摘要：有向网络的最短路问题在交通、通信系统的最优路径计算以及多阶段决策过程的最优轨线设计等实际问题中有着重要应用.经典模型及算法解决固定弧权条件下的最短路问题,而实际中,网络往往是动态的,即弧权依赖于时间变化,例如在交通拥堵时运行时间会变长,这时经典的最短路算法不再适用.文中证明了动态网络的最短路问题是NP-困难的;给出了最短路稳定性的充要条件,并在此基础上提出一种基于稳定区间的近似算法,通过模拟实验验证了该算法的有效性.

摘要：通过引入两个数组,从提高算法效率和增强寻路直观性两个方面对无回路网络最短路问题的权矩阵法进行了改进。改进后的算法既能快速的计算从源节点到其目的节点的最短路权又能更直观的找出最短路。最后算法分析和仿真结果表明,改进算法较权矩阵法相比,运算速度有了明显的提高,是计算无回路网络最短路的一种有效算法。

摘要：最短路权矩阵法是通过权矩阵计算来实现Dijkstra算法的一种方法。针对权矩阵法在大型网络应用中的不足,从提高算法效率和增强寻路直观性两个方面对其进行了改进,并给出了新的算法。新算法既能快速计算最短路权又能更直观地找出网络中的最短路,是一种计算最短路的简捷方法。仿真结果和算例表明了新算法的有效性。

摘要：针对Hamming距离下的最短路逆问题,分析了最优解的性质,给出并证明了问题存在可行解的充分必要条件;利用把背包问题的实例多项式归约到该问题的实例,证明了该问题为NP困难的,为设计该类问题的近似算法提供了理论依据.

摘要：目的　给出一些计算赋权图中任意两个节点之间最短路的算法。方法　利用矩阵方法。结果　给出了赋权图中任意两点之间最短路的算法;任意两点之间在含有最少边数情况下的最短路算法;赋权图中的所有最短路算法,以及前N条最短路的算法。结论　所研究的算法解决了传统算法的某些不足,因基于矩阵运算,程序设计简单,实用性强。

摘要：分析大城市公共交通网络图的特点 ,提出了乘公共交通在大城市观光旅游时的乘车路线问题 ,并应用图论的理论和方法 ,通过建立数学模型 ,给出最佳乘车路线的设计方法 .本文的方法和结果可以应用在城市公共电脑服务系统中、公共线路的设计上、公交线路网络图的评价和改造上等 .

摘要：提出一个解带权区间图的最短路问题的 O(nα(n) )时间新算法 ,其中 n是带权区间图中带权区间的个数 ,α(n)是单变量 Ackerman函数的逆函数 ,它是一个增长速度比 log n慢得多的函数 ,对于通常所见到的 n,α(n)≤ 4 .本文提出的新算法不仅在时间复杂性上比直接用 Dijkstra算法解带权区间图的最短路问题有较大改进 ,而且算法设计思想简单 。

摘要：最短路问题是网络设计中的一个基本问题,当前研究工作都基于边的权值是确定的这一假设。论文研究边的权值是一区间数时的最短路问题,利用优化理论,建立了目标函数系数在区间上均匀分布的模糊线性整数规划模型。通过引入正、负理想点概念,将模型转化为具有确定系数的单目标优化问题,给出了求解算法,并证明了算法的时间复杂性是多项式时间的。仿真实例说明了模型和算法的有效性。

摘要：针对传统的Floyd算法难以解决中国教育网的平均最短路径长度计算问题,在对网络进行度分析的基础上,设计了一种宽度优先搜索(BFS)并行算法,该算法可有效地避免对出度为0的节点进行搜索,采用VC编写基于MPI(MessagePassingInterface)的并行程序,通过20台电脑连网计算分析,该方法取得了令人满意的结果。

摘要：最短路问题是组合优化中的经典问题之一,对其设计有效的算法具有广泛的应用价值和重要的理论意义．为了减少对初始种群选取的限制,扩大种群的多样性,本文提出了一种新的杂交方式．根据一对染色体中不同位相同基因对的数目,设计了分类杂交．这种杂交不仅增加了种群的多样性,还避免了不可行解的出现．与杂交算子相对应设计了具有局部搜索功能的收缩—扩张式变异算子,使得本算法效率有了极大提高,并在理论上证明该算法以概率1收敛到全局最优解．最后的数值试验也表明此算法是十分有效的．