Research On The Methods Of The Shortest Path Query

The shortest path query is one of the hot issues in graph research,and it plays a distinctly essential and significant role in many fields,including urban transportation network,social network and bioinformatics network.At present,there are two types of shortest path query algorithms,one is the exact shortest path query,and another is the approximate shortest path query.This paper mainly studies the exact shortest path query problem.The main research items in this dissertation are as follows.Firstly,through the analysis of the existing algorithms,we find that the existing algorithms have the problem of low efficiency and expansibility which caused by the long time of the index construction and the large scale of indexes.Secondly,in the aspect of index construction,three index construction strategies are proposed.Constructing a vertex-related index for the vertices with degree equal to one,constructing a path-related index for the vertices on a single path,and proposing a method of constructing a 2-hop tag index based on partial vertices for the rest vertices,thus,we can reduce the scale of the indexes and the time to build the indexes by reducing the redundant storage of the data and the frequency of the graph traversal.Thirdly,in the shortest path query,we put forward the corresponding query strategy for different index construction strategies.For the vertex-related index,the shortest path query is answered by the vertex relationship and the 2-hop label;For the path-related index,the shortest path query is answered by the path relationship and the 2-hop label;For the partial 2-hop label indexes,the shortest path query is answered by the 2-hop label in conjunction with the graph traversal.Finally,we conduct experiments on the 15 real data sets to test,the experimental results verify the high efficiency of the method presented in this paper compared with the existing methods from the following aspects,such as the time of the index construction,the index scale,the query response time and so on.