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

Fast Pruning Algorithm for Unreachable Vertices and ItsApplication in Solving Shortest Path Problem

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

k step reachability query is used to solve the problem whether there exists a reachable path from vertex u to vertex v within k steps in graph G.But these reachability studies mostly focus on unweighted graph.This paper builds three indexes:the earliest arrival index,the reverse earliest arrival index,and the latest arrival index in the weighted graph and employs these three indexes to achieve fast pruning of the unreachable vertices,so as to effectively reduce the scale of the weighted graph.The time and space complexities of the method are O(n+e)and O(n),where n and e are the number of the verices and the edges of graph G,respectively.This method combined with algorithms Dijkstra,Floyd,and A-star is utilized to solve the shortest path problem in order to improve the perfomance of the triditional algorithms.Finally,a logistics distribution network is employed to verify the performance of the proposed algorithm.The experimental results show that the proposed algorithm can accurately and efficiently prune the useless vertices and boost the calculating speed of the shortest path effectively,the effectiveness of the proposed method is verified.