Research On Shortest Path Query Algorithm For Large Graph

The shortest path query is used to get the shortest path between two points in the graph.It is one of the core operations in graph data management,and it has always been a hot issue for researchers.The shortest path query is widely used in traffic road networks,social networks,and biological information networks to analyze data.With the continuous increase of the scale of data graphs and the continuous expansion of application fields,the further improvement of the efficiency of shortest path query processing is a key issue to be solved urgently.This thesis studies the shortest path query problem for undirected and unauthorised graphs.The specific research is as follows:Firstly,according to the characteristics that the actual data graph is sparse and obeys the power law distribution,a strategy for segmenting the original graph and processing separately is proposed.The strategy first removes the single-path path from the original image to get a scale-down graph.For a single path,the vertex is encoded with the relative position of the vertex in the path,and the shortest distance between the vertices in the path is quickly calculated.For the compression map,construct a map index of the landmark label based on the compression map to quickly solve the shortest path of the vertex pair on the compression map.Secondly,based on the single-path path index and the compressed graph index,an efficient short-path path solving method is proposed.The basic idea of the method is:given two query points,if the two points are located in a single-path path or a compressed map at the same time,use the corresponding single-path path index or landmark label index for fast solution;otherwise,first find two The vertices are the proxy points on the compressed graph,and the final query answer result is obtained by calculating the shortest path between the proxy points and the shortest path of the proxy point and the query point.Finally,the real-time data set is need test and verify.The time and scale of the indexing of the tag and the response time of the query are compared with the existingmethods to analyze and verify the efficiency of the proposed method.