最短路径树的计算与修改算法

在有向赋权图Ｇ＝（Ｖ，Ｅ，ＣＯＳＴ）上，给出了求解以每个顶点为根的向前／向后最短路径树（ＦＢＳＰＴ）算法。当Ｇ中的边被删除或边权增加时，证明了在这种情况下，不可能存在高效的对ＦＢＳＰＴ的修改算法；而对边添加和边权减少的情况，本文给出时间复杂性为Ｏ（ｎ￣２）的修改算法。此外，本文也讨论了对上述算法的并行实现问题。     

用O(tlogt)的连接图求有障碍时的最短路径

针对有障碍时求两点间的最短路径这一问题,提出了极区和自由区的概念,并由此构造出一种新的强连接图ＣＦ,它由自由区的特征边和障碍的极边构成,其顶点数为Ｏ（ｔ）,边数为Ｏ（ｔｌｏｇｔ）,其中ｔ为障碍的极边数,而现有最佳连通图的顶点数和边数为Ｏ（ｔ＾２）,同时提出了时间复杂度为Ｏ（ｔｌｏｇ＾２ｔ）的高效ＧＦ构造算法,并使用“不改向”的启发式Ａ算法在ＧＦ中寻找两点间的最短路径。     

求图中顶点之间所有最短路径的一种算法

提出求一个顶点到另一个顶点的所有最短路径的一个算法.该算法利用图中每个顶点的出度的变化,来动态修改每个顶点到目的结点的最短路径长度,用C+ +编制了相应程序验证该算法的正确性和高效性,该算法容易理解,降低了时间复杂度.     

完全欧几里德距离变换的最优算法

欧几里德距离变换（ＥＤＴ）对由黑白素构成的二值图象中所有象素找出其到最近黑素的距离，应用于图象分析，计算机视觉，在本文之前，该问题的最好复杂度为Ｏ（ｎ＾２ｌｏｇｎ）。本文提出了一个复杂度为Ｏ（ｎ＾２）的算法，使复杂度达到最优，该算法可以并行化，在有ｒ个处理单元的ＥＲＥＷＰＲＡＭ计算模型上，若ｒｌｏｇｒ≤２２／６ｎ，则时间复杂度为Ｏ（ｎ／ｒ）否则为Ｏ（ｎｌｏｇｒ）。     

最长公共子充列问题的改进快速算法

现在几个最常用的解决最长公共子序列（ＬＣＳ）问题的算法的时间复杂度分别是Ｏ（ｐｎ）,Ｏ（ｎ（ｍｐ））。这里Ｍ、ｎ为两个待比较字符串的长度,Ｐ是最长公共子串的长度。给出一种时间复杂度为Ｏ（ｐ（ｍｐ））,空间复杂度为Ｏ（ｍ＋ｎ）的算法。与以前的算法相比,不管在Ｐ〈〈ｍ的情况下,还是在Ｐ接近Ｍ时,这种算法都有更快的速度。     

不可达顶点剪枝算法及其在最短路径中的应用

[k]步可达性查询用于回答图[G]中从顶点[u]到达顶点[v]最多[k]步是否存在路径,但其多用于无权图的可达性研究。针对加权图,在图中构建了最早到达、逆向最早到达和最晚到达等三个索引,并应用这三个索引实现对不可达顶点的快速剪枝,从而有效地缩减了加权图的规模。运用该方法建立索引并剪枝顶点的时间复杂度与空间复杂度分别为[O(n+e)]和[O(n)],这里[n]和[e]分别为图中顶点的数目和边的数目。该方法可以与Dijkstra算法、Floyd算法和A*算法等多种传统算法相结合,并应用于最短路径求解,从而提高传统算法计算性能。最后以物流配送网络为例进行了实验验证,实验结果表明提出的方法可以正确并高效地对不必要计算的顶点进行剪枝,从而加快了最短路径求解速度,验证了提出方法的有效性。     

基于CREW遍历图的一种并行算法

针对串行算法模型下基于顶点遍历图的情况,提出了一种在CREWPRAM并行模型下遍历无向图的算法。该算法是找出无向图的一棵最短路径生成树,由向上和向下两条有向边替换最短路径生成树的每条边形成欧拉回路,运用欧拉回路技术计算前缀和,前缀和所对应的顶点即为遍历无向图的顺序。得出了该算法时间复杂度为O（n＋logn）的结论。     

一种基于分层图的改进SPFA算法

针对数据结构课程教学中顶点数受限的最短路径问题,提出一种基于图分层的改进SPFA算法——K_SPFA。借鉴图分层思想,将原图拓展为层数与顶点限制数相等的图层,将原图中的边拓展成图层间的边。利用2个同步循环的FIFO队列和贪心策略,对SPFA算法的数据存储结构和最短路径更新操作进行改进,从而实现原图中顶点数受限的最短路径寻找。实验结果表明,K_SPFA具有较低的平均时间复杂度。     

用Θ(t)的广义连接图求有障碍时的最短路径

在有障碍时求两点间的最短路径是VLSI设计、机器人设计等领域中的基本问题，连接图是研究此问题的基本工具，现有算法构造的最好的连接图GF是基于自由区的概念而设计的，其顶数和边数分别为O（t)和O（tologt)，其中t为障碍的极边数，提出了广义自由区和极大正规划分的概念，在此基础上得到广义连接图GG，用来表征广义自由区之间的邻接情况，其顶数和边数均为Θ（t)，且具有平面图的性质，同时还提出了基于扫描线的极大正规划分构造算法，其时间复杂度为O(tlogt)；并提出规范路径的概念；以及采用“不改向”启发式策略的A^*算法在广义连接图GG中寻找两点间的最短路径，算法的时间复杂度由于GF的现有算法的O(tlogt)降低到Θ（t)。     

求图中顶点之间所有最短路径的一种实用算法

提出了求一个顶点到另一个顶点的所有最短路径的一个算法，此算法中设计了一些独特的数据结构。在算法运行的整个过程中，求一个有效顶点（后面定义）到终点的所有最短路径的过程（入栈、出栈等操作）实际只进行一遍，用C语言编制的相应程序验证了这个算法的可靠性和实用性。     

一个多元选择算法

本文基于数排序的思想，从高位关键字开始，对ｍ位关键字的ｎ个记录进行扫描，给出了一个多元选择算法，算法的最坏复杂度为Ｏ（ｍ（ｎ＋ｒ）），但平均复杂度为Ｏ（ｎ＋ｒ）。     

利用多线程技术实现最短路径的并行算法

最短路径问题是图论中的一个典范问题,它被应用于众多领域.最短路径问题可以分成两类：单源最短路、所有顶点对间的最短路径.在研究图中最短路径问题上,Dijkstra算法是其中最为经典的算法之一,本文主要介绍所有顶点对间的最短路径问题,提出了一种更高效的新的所有顶点对间的并行算法.最后利用多线程技术对给出的并行算法进行了实现.     

Dijkstra算法在停车诱导系统中的应用

路径诱导是停车诱导系统中需要解决的关键问题,而路径诱导的本质就是求最短路径,Dijkstra算法可以很好地求解最短路径.传统Dijkstra算法采用邻接矩阵作为存储结构,算法的时间复杂度为O（n2）,存在搜索速度慢和浪费空间的缺点.为此,对传统Dijkstra算法进行了改进,采用邻接多重表作为存储结构,采用堆排序法的思想来寻找权值最小的顶点,算法的时间复杂度为O（nlog2n）.用改进后的算法在实际地图中进行仿真实验,结果表明,改进后的算法能更快、更有效率地找到两点间的最短路径.     

Voronoi图算法及其在混合电路的衬底耦合研究中？…

提出了对版图进行划分的Ｖｏｒｏｎｏｉ图的算法：将Ｖｏｒｏｎｏｉ图进行变换,通过扫描技术,从下到上对每个点与交点进行２,从而形成变换后的Ｖｏｒｏｎｏｉ图,最后将此图转换为Ｖｏｒｏｎｏｉ图。在 计算中,针对集成电路的物理特性,改进了阱区附近的Ｖ图的生成以及多个水平位置点和兼并问题。算法时间复杂度为Ｏ（ｎｌｏｇｎ）空间复杂度为Ｏ（ｎ）。     

求带多个限制条件的单源多权最短路径算法

带限制条件的多权最短路径问题具有广泛的应用。本文给出一个通过按字典序生成从源顶点到目标顶点的非支配路径的方法，求出满足限制条件的最短路径的算法，并且分析了算法的时间复杂度。     

Voronoi图算法及其在混合电路的衬底耦合研究中的应用

提出了对版图进行划分的Ｖｏｒｏｎｏｉ图的算法：将Ｖｏｒｏｎｏｉ图进行变换,通过扫描技术,从下到上对每个点与交点进行处理,从而形成变换后的Ｖｏｒｏｎｏｉ图,最后将此图转换为Ｖｏｒｏｎｏｉ图．在计算中,针对集成电路的物理特性,改进了阱区附近的Ｖ图的生成以及多个水平位置点和兼并问题．算法时间复杂度为Ｏ（ｎｌｏｇｎ）,空间复杂度为Ｏ（ｎ）．     

一种求受顶点数限制的最短路径的新算法

提出了一种基于逆邻接表求受顶点数限制的最短路径的新算法，其时间复杂度为O(m-2)^*w)(m是受限制的顶点数，w是有向图中弧的条数)，优于同类算法。采用逆邻接表作为图的存储结构，该算法很容易实现。     

可重构造的网孔机器上的k-选择

对于一个 ｍ ×ｎ（ｍ ≤ｋ）的列有序矩阵,文中在 ｎ × ｎ 可重构造的网孔机器上提出了一个并行 ｋ选择算法,其时间复杂度为 Ｏ（ｌｏｇ２ｍ ＋ ｌｏｇｍ ｌｏｇ２ ｎ＋ ｌｏｇ３ ｎ）,而对于一般的ｌ元集,文中在相同的模型下提出了一个时间复杂度为 Ｏ ｌｏｇ２ ｌｎ ＋ ｌｏｇ ｌｎ ｌｏｇ２ ｎ＋ ｌｏｇ３ｎ＋ ｌｎ ｌｏｇ ｌｎ 的并行 ｋ选择算法．当时 ｌ≥ Ｏ（ｎｌｏｇ３ｎ／ｌｏｇ ｌｏｇｎ,该时间复杂度为 Ｏ ｌｎ ｌｏｇ ｌｎ ．特别地,当ｌ＝ Ｏ（ｎ１＋ ε）（ε＞ ０ 为常数）,则时间复杂度为 Ｏ ｌｎ ｌｏｇｎ ．此时达到的加速比为 ｎ／ｌｏｇｎ．     

求受顶点数限制的最短路径问题的一个算法

提出了求受顶点数限制的最短路径问题的一个算法,与现有的算法相比,该算法效率较高,时间复杂度为O((k-2)m^2)(k是受限制的顶点数,n是图中顶点总数),而且该算法比较简单,易于描述,实现和理解.     

图的最短路径和传递闭包的并行算法

1.图的最短路径 给定一赋权有向图G=(V,E),假设G中没有带负权圈的顶点,Floyd给出了一个计算G的所有顶点对v_i,v_j之间最短路径算法。在该算法中,用带权邻接矩阵cosT表示图,并规定cosT(i,j)=∞若(i,j)不属于E和cosT(i,j)=0,i,j=0,…,n-1,该算法的设计思想是按下面的递推规则依次产生矩阵序列A~0,…,A~(n-1),其中A~(n-1)即是G的所有顶点对之间最短路径的长度。