关键词: 索引, 剪枝策略, 最短路径, 可达性查询

Abstract:

[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.

Key words: index, pruning strategy, shortest path, reachability query