一种改进的Dijkstra算法的分析及程序实现

Dijkstra算法是求有向图中从某一源点到其余各点最短路径的算法。本文通过对传统的Dijkstra算法进行分析,提出一种改进算法,经理论分析,对于顶点数较多而边数较少的有向稀疏图来说,在求最短路径时能够大大提高算法的运行效率。     

时态图顶点介数中心度计算方法

在社会网络分析中,介数中心度用于衡量顶点对网络结构的贡献大小,是一种广泛使用的顶点重要度衡量指标.该指标主要通过计算经过顶点的最短路径数来表明顶点的重要性.目前研究的介数中心度算法主要聚焦在普通图上,针对时态图的研究工作较少.普通图介数中心度计算方法主要依据Brandes算法设计,Brandes算法有效的关键理论是最短路径的子路径依然是最短路径,即最优子结构特性.然而时态图包含时态信息,时态路径类型多样,并且时态最短路径并不满足此特性,因此普通图介数中心度计算理论与方法不再适用于时态图.鉴于此,定义了严格（时态递增）和非严格（时态非递减）2种时态路径类型,并研究了时态图介数中心度计算理论与方法.提出了一种高效的基于消息传播的2阶段迭代计算框架.第1阶段采用自顶向下的广度优先遍历方式计算时态最短路径;第2阶段采用自底向上的方式计算顶点的后继节点和孩子节点对其介数中心度的贡献值,并设计了基于消息传播机制的迭代累积计算方法.为了提高效率和可扩展性,实现了基于OpenMP(open multiprocessing)框架的多线程并行算法FTBC(fast temporal betweenness...     

GIS中最短路径算法的研究以及在VB中的代码

本文针对GIS中网络拓扑图的一般特点和对网络分析实时性的要求,主要以Dijkstra最短路径算法为理论基础,改进原有最短路径算法中对最小权值的顶点的搜索策略,提出一种实用的Dijkstra最短路径算法的实现方法,并在VB环境下用代码实现。     

SPFA算法的分析及改进

SPFA(Shortest Path Faster Algorithm)算法是一种对任意有向图求单源最短路径的算法。该算法实现简单,实际运行效果较好,在国内有着比较大的影响力。但遗憾的是,该算法一直缺少正确的理论分析。对该算法进行了分析,指出该算法在不存在源点可达负圈的有向图中,最坏情况运行时间为Θ(|V||E|);在存在源点可达负圈的有向图中,算法将无限运行下去。对此,给出了改进的SPFA算法,对于任意的有向图,该算法能够在O(|V||E|)内运行完毕。最后,从实际运行角度将SPFA算法与其它思想上同源的最短路径算法进行了一系列比较。     

求图中受顶点数限制的所有最短路径的算法

提出了图中从一个顶点到另一个顶点的求受顶点数限制的所有最短路径的一个算法,算法基于逆邻接表,最短路径生成树和叶子指针链表等几种特殊的数据结构.对算法进行了详细的理论分析,分析结果表明该算法实现简单、效率较高,且易于描述、实现和理解,并用C语言设计了相应的程序验证了该算法.     

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

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

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

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

Dijkstra算法求解最短路径的设计与实现

对任意图,选择合适的数据结构表示图,在此基础上实现求解最短路径的Dijkstra算法。对所设计的图的数据结构,提供必要的基本功能。建立图的表示模块,顶点的插入和删除操作模块;在建立图之后从单源点开始求最短路径并显示。实现的功能有建立有向图,排除和增加目的地,方便找出最短路径,在建立好的有向图中,显示出来从顶点到各个顶点的最短路径。     

基于随机游走的大规模图中节点对采样算法

社会网络中的节点对采样可用于大规模社会网络的好友预测和用户兴趣识别.当整个网络的拓扑结构不完全或者随机选择用户的代价很高时,传统的均匀顶点采样方法的性能迅速下降.为此,提出了一种基于随机游走的大规模图中节点对采样算法.首先对社会网络的节点对采样进行了系统分析,对不同跳数下的节点对进行了定义;然后将社会网络转换成等价的网络图.新图中的顶点是原图中的边,新图中边的两个顶点是原图中含有相同顶点的两条边.最后,在新图上应用随机游走模型对节点对进行采样.实验结果表明,提出的方法统计误差小、执行效率高,性能明显优于均匀节点采样的相关算法.     

用元胞自动机求最短路径的一种新算法

在一个基于元胞自动机模型的求图中一个顶点到另一个顶点的最短路径的算法的基础上,分析出:它的关键部分(即演化规则)中"减最小剩余权"这一重要步骤与求图中一个顶点到另一个顶点的经典的最短路径算法的基本思想相距甚远,应该省去.在提出的新算法中省去"减最小剩余权"这一重要步骤,这个改进较大地提高了算法的效率.最后通过举例子分别用两个算法进行求解,通过这些求解步骤的对比,明显看出本算法的正确性和高效性.     

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

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

三角网格模型上任意两点间的近似最短路径算法研究

提出一种任意三角网格模型上两点间的近似最短路径算法．该算法首先将三角网格模型表示为带权图结构，然后用Dijkstra算法计算带权图中两顶点间的最短路径，并将其作为网格模型上该两点间最短路径的初始近似．通过不断地迭代对相关三角形边进行自适应细分，并构造每次细分后新的带权图，从而对网格模型上的两点间最短路径进行迭代逼近．该算法效率高，可以很好地控制精度，适用于大型三角网格模型两点间最短路径寻找．文中还讨论了该算法在任意三角网格模型区域划分中的应用．     

Dynamic algorithms for the shortest path routing problem: learning automata-based solutions.

This paper presents the first Learning Automaton-based solution to the dynamic single source shortest path problem. It involves finding the shortest path in a single-source stochastic graph topology where there are continuous probabilistic updates in the edge-weights. The algorithm is significantly more efficient than the existing solutions, and can be used to find the "statistical" shortest path tree in the "average" graph topology. It converges to this solution irrespective of whether there are new changes in edge-weights taking place or not. In such random settings, the proposed learning automata solution converges to the set of shortest paths. On the other hand, the existing algorithms will fail to exhibit such a behavior, and would recalculate the affected shortest paths after each weight-change. The important contribution of the proposed algorithm is that all the edges in a stochastic graph are not probed, and even if they are, they are not all probed equally often. Indeed, the algorithm attempts to almost always probe only those edges that will be included in the shortest path graph, while probing the other edges minimally. This increases the performance of the proposed algorithm. All the algorithms were tested in environments where edge-weights change stochastically, and where the graph topologies undergo multiple simultaneous edge-weight updates. Its superiority in terms of the average number of processed nodes, scanned edges and the time per update operation, when compared with the existing algorithms, was experimentally established. The algorithm can be applicable in domains ranging from ground transportation to aerospace, from civilian applications to military, from spatial database applications to telecommunications networking.     

具有树和路约束的平行机排序问题

考虑具有树和路约束的平行机排序问题,其工件集对应于无向图(有向图)的边(弧)集。目标是选取工件集的一个子集使其满足树或路的约束,将其放在平行机上处理,使得机器的最大完工时间(makespan)尽可能地小。通过分析此类问题的组合性质,得到如下结论：在K-树约束下,利用最小支撑K-树的性质可得一个有效多项式时间近似方案;在两固定点间路的约束下,通过构造辅助实例以控制边的权重,分析辅助实例的输出值与目标实例最优值之间的关系,利用最短路的性质可以得到一个2-近似算法;在单源点最短路径树的约束下,根据最短路径树的性质可以得到一个有效多项式时间近似方案;在两固定点间最短路的约束下,在所有的两点间最短路构成的子图基础上,通过构造新的辅助图以控制弧的权重,再利用最短路的性质可以得到一个1.618-近似算法。     

一种计算因特网AS拓扑的最短路径的快速算法

最短路径是因特网AS(autonomous system)拓扑的一个重要特征,AS间的路由路径一般是AS之间的最短路径.因特网服务提供商之间复杂的商业关系导致AS之间存在复杂的路由关系,从而影响AS路由路径的选择,因此在计算AS拓扑中最短路径时需要考虑AS间的路由关系.提出了一种计算AS拓扑中最短路径的算法,算法基于无向图的宽度优先最短路径算法,时间复杂度为O(nm),这里n和m分别为拓扑图中节点和边的个数.通过实验发现,与现有的计算AS拓扑最短路径的时间复杂度为O(n3)的算法相比,该算法在实现同样精确度的前提下大幅缩短了计算时间.     

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

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

三角网格表面任意两点间并行近似测地线算法

为降低求解三角网格表面任意两点间近似测地线长度和路径问题的时间开销,提出一种基于局部细分法的并行近似测地线算法。采用类矩阵乘最短路径并行算法求解点对间初始最短路径,并用源分割法映射子网格数据;所有处理器并行执行,对其所拥有点对之间的初始最短路径周围三角面片上的边进行细分操作;最后基于局部细化后的细分图并行,求得所有点对间的近似测地线长度和路径。实验结果表明,该并行近似测地线算法能够有效降低求解该类问题的计算时间,计算效率大大提高。     

An intelligent search path

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) such that the sum of the weights of its constituent edges is minimized. An example is finding the quickest way to get from one location to another on a road map; In this case, the vertices represent locations and the edges represent segments of road and are weighted by the time needed to travel that segment. In this paper, a simple method to find the shortest path in a fuzzy environment is proposed. Here the edge weights of the network are considered as fuzzy numbers so that the imprecise data values can be represented. © 2010 Wiley Periodicals, Inc.     

切换到高一层路网最近四个点的最短路算法

针对基于大规模图的最短路问题求解速度慢的问题,提出了一个基于路网等级的求最短路的快速近似算法。该算法首先求出高一层路网到起点的4个最近点和到终点的4个最近点及最短路径,由高一层路网形成的子图T再加上这8个最短路径形成图T',在T'上求起点到终点的最短路。这种设计使得该算法适合在超大规模图上求解,理论上也证明了精度可控,同时预处理数据也是可行的,从而使两点间最短路的求解速度大大提高。在纽约公路网上的测试结果说明了该算法的有效性和合理性。