求赋权图上最小树的两个算法

该文证明了赋权图上的树为最小树的一个充要条件，并由此得到求赋权图上最小树的两个算法。     

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

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

赋权多阶段有向图最短路的求法

多阶段有向图是常见的一种有向图,许多运输、工程、管理等实际问题能转化为有向图最短路问题进行求解,尤其赋权多阶段有向图对解决该类实际问题更具有重要意义.研究了赋权多阶段有向图的最短路问题,从图上逆序标号法、表上作业法和动态规划法不同的角度对文中实例给出了赋权多阶段有向图最短路求解方法。     

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

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

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

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

赋权图中重路的隐赋权度条件

对2—连通非Hamilton赋权图G，本文给出了重路存在的隐赋权度条件：将G满足文中描述的条件C1、C2，且max{id^u(u),id^u(v)|d(u,v)=2}≥m/2,则当G中存在y—最长路时，存在一最重的y—最长路P(x，y)满足d^u(x)≥m/2.     

赋权图中最重的最长v-路与赋权周长

对2－连通非Hamilton赋权图G,本文证明：若P（u,v)是G中最重的最长路，则G的赋权周长C^w(G)≥d^w(u) d^w(v)，假设G满足文中描述的额外条件C1，C2，则max｛d^w(x),d^w(y)|d(x,y)=2｝≥m/2时，对每个顶点v,G含量最重长v-路P（u,v)使d^w(u)≥m/2，而d^w(x) d^w(y) d^w(z)≥m（当d(x,y,z)=2)时，c^w(G)≥2m/3.改进了非赋权图的周长及赋权图的赋权周长的若干已有结果。     

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

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

赋权连通图的最小树图的连通情况

以G的生成树为点,两点相邻的充要条件是两颗生成树只相差一条边,这个图称为G的生成树图。连通图的生成树图是连通的,本文对此进行推广,证明了赋权连通图的最优树图也是连通的。     

赋权图的区间着色和图的着色算法

本文提出了图的区间着色模型,并对相容性图给出了区间着色的多项式算法,同时改进了求图的着色问题的算法。     

新的k最短路算法

在无向图上,对于任意源点—目的点点对,给出了一个新的k最短路算法. 这一算法按长度递增给出k最短路路径. 算法的复杂度为O(m+nlgn+mlgk). 这一算法基于动态规划,首先计算出每一点到源点的最短距离,然后从目的点回溯到源点. 根据各点的最短距离信息,给出一棵以目的点为根节点,源点为叶子的树表示的k最短路路径.     

基于Dijkstra算法的一种最短路径改进算法

本文在Dijkstra算法的基础上,增加了一些数据结构,提出一种能直观地求出从一个顶点到其它各顶点的所有最短路径的算法。     

PL/SQL在求解最短路径问题中的应用

图论中的一个典型的问题就是最短路径和最小代价问题.本文介绍了一种基于Oracle的表、视图及存储过程求解最短路径(最小代价)的方法,该方法使得解决复杂的有向图问题更加容易,而且不需要很多代码.     

有负权时有向图全路径算法研究

有向图有负权路径求解问题比较常见,但求所有可达路径的算法却见之甚少。本文在以前提出的一种有向图无负权所有可达路径搜索算法的基础上,提出一种先将有负权问题转换成无负权问题,进而用无负权算法求解之的方法。     

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

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

邻接矩阵求带权图中最短通路

通过对带权邻接矩阵定义一种运算,计算n阶简单带权图中任意两点之间步长为1,2,…,n -1的最短通路长度,逐步比较,确定通路所过各边权值之和最小的即最短路径。在计算的过程中用矩阵记下最短路径所经过的所有结点,最后验证了其在无向和有向简单带权图中的有效性。     

边染色图中的长彩色路问题

研究了边染色图中的彩色路,给出了满足一定色度条件下的边染色中彩色路的长度的下界。     

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

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

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

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