无向图中严格第三短路问题的多项式时间算法

给定一个无向图G=（V,E;w;s,t）,其中s,t是2个固定顶点,w：E→R^＋是边的长度函数．最短路是指所有路中长度最小者,次短路是指长度比最短路严格大的所有路中的最小者,严格第三短路是指长度比次短路严格大的所有路中的最小者．对正权重无向图中严格第三短路问题给出一个O（n^4）多项式时间算法．     

能源综合输送系统规划的模型与算法

为能源综合输送系统的规划构造了一个网络模型。以年计算费用来综合投资与年 运行费，则最小费用是流的二次三项式函数，在线性最小费用流算法的基础上可以进 行优化。 该模型曾用于山西能源基地的输煤输电规划。     

最短路的蚁群算法收敛性分析

蚁群算法最初出发点是模拟蚂蚁觅食,蚂蚁可以利用局部信息素的变化找到从蚁穴到食物的最短路。对求解最短路问题的蚁群算法的收敛性进行了探索性分析,定理给出了寻找最短路的蚁群算法收敛的充分条件,并通过一个数值例子验证了该结果。     

矩阵方法求赋权图中最短路的算法

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

求解路网最短路的快速算法

探讨了最短路算法在交通分配中的重要地位。在此基础上．比较了现有最短路算法的优缺点,同时提出了一种改进的矩阵迭代算法．并利用该算法对一简单路网进行了验证。     

运费有差异的多品种流交通网络最小费用算法

对运费有差异的多品种流交通网络进行了分析,构建了复合参数和复合指标,借鉴连续最短路算法和FordFulkerson算法,设计了运费有差异的多品种流最小费用算法,并通过算例证明了算法的可行性,为解决实际交通网络的相关问题提供了参考.     

寻求中国货郎担问题最短回路的多项式时间算法

研究求解中国货郎担问题最短回路的多项式时间算法。首先利用计算机几何凸壳与中轴的结构将集划分尤其中干个子点集,然后反复采用求子点集凸壳及划分科余子点集的方法,求得通过子点集的子路径,最后将各子路径连接成一条回路。中国货郎担问题存在多项时间算法求得最短回路。     

网络最短路的提速问题

网络最短路提速问题起源于交通运输、计算机信息传输等领域,具有重要的理论和实际应用意义.对一般网络来说,该问题是NP-完全的.对(0,1)-提速问题的指定路线的提速问题两种情况分别进行了研究,证明了(0,1)-提速问题是NP-完全的、一般网络在指定路线情形下的提速问题是多项式可解的,给出了单源多汇网络G中提速问题的O(nm log n)算法.     

最短路径及其变形问题的算法

讨论了一个带权图的最短路径的算法及其若干个变形问题的算法，并在MATLAB软件环境下对最短路径问题给出了一个简捷易懂的程序。这些算法在实际应用中有较强的实用性。     

一种求解时变条件下双目标最短路的算法

在组合优化过程中,往往需要获得从起点到终点之间的最短路,有时需要同时考虑两个目标,而这些目标可能会随着时间的变化而变化。为此,提出了一种利用标号法获得时变条件下双目标最短路的方法,考虑了不同的出发时间的情况,并对算法的复杂性进行了分析,最后给出了一个应用算例。     

基于最小生成树算法求解图的单源最短路径的研究

对《基于Kruskal算法的最短路径算法研究》一文中提出的方法进行探讨,通过构造实例论证了Kruskal算法并不能直接用于求解有向带权图的单源最短路径问题,并综合性地对基于最小生成树算法求解图的单源最短路径问题进行分析,通过构造实例最终得出最小生成树算法不适用于求解图的单源最短路径问题的结论.     

基于最小生成树算法求解图的单源最短路径的研究

对《基于Kruskal算法的最短路径算法研究》一文中提出的方法进行探讨,通过构造实例论证了Kruskal算法并不能直接用于求解有向带权图的单源最短路径问题,并综合性地对基于最小生成树算法求解图的单源最短路径问题进行分析,通过构造实例最终得出最小生成树算法不适用于求解图的单源最短路径问题的结论.     

模糊最短路问题的一种新算法

作者讨论了从一个指定点到另一个指定点的最短路问题,其弧长都是不精确的模糊数.利用模糊数的某种序关系,作者提供了一种新算法来处理模糊最短路问题,该算法由基于中心点的模糊数比较方法构成,基于中心点的模糊数比较方法可找到模糊最短路长,并获得相应的模糊最短路径.作者给出了4个解释性的实例并验证了算法的可行性.     

时变网络中零等待时间最短路问题的一个对偶算法

时变最短路问题是最短路问题的一个推广.假设图G=(V,A)是一个有向图且有唯一的源点t,图G中的每条弧(i,j)∈A都附有两个参数:弧的传送时间b(i,j,u)和弧的传送费用c(i,j,u),它们都是在弧的顶点i上的出发时间u的函数.找出从源点到其它各点的最短路,即最小费用的路,并且要求每条最短路的传送时间不能超过给定的时间限制T.假设除源点外,在其它任何顶点都不能等待,b(i,j,u)是满足u b(i,j,u)≥0( (i,j)∈A,u=0,1,…,T)的任意整数,c(i,j,u)是任意的非负整数.给出了该问题的原规划和对偶规划,提出了一个最优性条件和一个对偶算法,并用一个数值例子来阐述算法.     

赋权图上最短路径的一种简便算法

在不考虑负回路的前提下,给出了在含有负权的赋权图上求任意两点间最短路径的一种简便算法,此算法既适用于有向图又适用于无向图,并且可据此算法找到最短路径。     

一类基于模糊图论的费用与时间最优化问题的模型

在寻求工程实施的最小时间和费用等最优化方案时，构造了多因素隶属度PERT图和隶属函数模型；并运用模糊约束量来解决带最小化时间因素的最小费用流问题。     

用最短路径法求关键路线及其SAS的实施

利用网络工程的关键路线为耗期最长的特点，将其按照一定的规则转化成最短路径问题，然后利用求最短路径的SAS程序，顺利地求出网络工程的关键路线。     

求解最短路径问题的一种改进的人工蜂群算法

针对传统算法在计算大规模路网的优化问题时所表现出来的计算时间长、存储空间大等缺点,提出了一种改进的人工蜂群算法来求解最优路径选择的方法．试验结果表明,对于有向图和无向图,该算法都具有较好的全局寻优能力,即能获得满足条件的最优路径．