关于最短路径算法

本文先为两个经典的最短路径算法补充具体路径的保留办法。然后,提供一个便于实现的求有向图两点间所有路径的算法.     

用遗传算法求解最短路径问题

文章应用遗传算法求解图论中的最短路径问题，并提出了该算法在解决这一问题中的一些处理方法，使用该算法可以很快地求出一批最短路径集。文中最后给出了算法运行结果及总结。     

增删边对最短路径影响的研究

在有向图中加入或删除一些边时,可能有多种可选的方案,通过对各种方案影响最短路径的大小进行研究;给出联通权重值的定义和对最短路径贡献大小的规定,并给出在多种可能方案中选择最佳方案的具体算法。     

和声搜索算法在求解最短路径问题中的应用

提出了一种改进的全局和声搜索算法来解决最短路径问题.首先,定义了动态基因突变率,并引入到和声搜索算法中,有效地阻止了算法陷入局部最优解.其次,应用动态优先值编码方案,根据和声向量中变量对应节点的优先值来构造路径,通过迭代更新和声记忆库,并最终获得最短路径.对由20～100个节点构成的网络拓扑进行仿真实验,应用三种性能指...     

增删边对最短路径影响的研究

在有向图中加入或删除一些边时,可能有多种可选的方案,通过对各种方案影响最短路径的大小进行研究;给出联通权重值的定义和对最短路径贡献大小的规定,并给出在多种可能方案中选择最佳方案的具体算法     

基于极小代数赋权有向图最短路径求解算法

应用极小代数给出了求解简单有向赋权图最短路径问题的代数算法.该算法基于赋权有向图的直接距离矩阵A,在极小代数意义下计算k步最短路径距离矩阵Ak和最短路径距离矩阵A+,并依此确定出赋权有向图的最短路径以及最少步数最短路径.与Dijkstra算法相比较,所提出的代数算法求解路径规划问题能够较快地得到特定的最短路径及其长度.     

TSP最短路径的必要条件初探

对于被访问城市数为n的不对称旅行商问题,构造了一个n行和n列的方阵,每一行上的n个元素为同一个被访问城市;每一列上的n个元素为n个互不相同的被访问城市.依次从该方阵的第一列到第k列上各取出一个城市,同一行上不存在两个被取出的城市,这样取出的城市序列就构成了一条长度为k的路径.主要讨论最短路径的性质:如果一条长度为(n-1)的最短路径能被产生,则该路径上的任一长度为k的路径都为最短路径,k=1,2,…,n-2.该性质为旅行商问题算法研究的基础.     

赫伦定理在最短路径问题上的应用

本文利用赫伦定理,求作了一类最短路径问题。     

最短路径算法在校园地理信息系统中的应用

本文介绍了求最短路径的迪杰斯特拉算法和弗洛伊德算法,并以地理信息数据为基础,以网络模型图为背景,利用弗洛伊德算法建立邻接矩阵D和路径矩阵P,最终求出任意两个位置的最短路径以及中间所经过的中转点。     

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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