Research Of Shortest Path Algorithm Based On Query Load Frequency

The shortest path problem is a fundamental computing problem in road networks with many applications such as GPS navigation,POI recommendation,and route planning services.Dijkstra's algorithm is a widely used approach to solve the shortest path problem.Given a origin s and destination t,it visits other vertices in non-decreasing order of their distances to s and terminates when the destination t is reached.Although this algorithm is simple and accurate,it has a high complexity making it impossible to apply to large-scale networks such as road networks.Therefore,researchers utilize index-based methods to solve the problem of high search cost.Among these index-based algorithms,label based algorithms have advantages over other methods.They arrange a label for each vertex such that the shortest distance between two vertices can be computed in linear time.When constructing the index,existing shortest path algorithms only consider the topological structure of networks and ignore the periodicity and regularity of the shortest path queries,which cause the redundancy of index and waste of resource.The shortest path algorithm based on query load frequency first predict the demand of regions and obtain the query frequency of each vertex.Then,it reduce the average time of the shortest queries by decreasing the label sizes of high-frequency vertices.In the demand prediction,the multi-task contextualized spatial-temporal network(MT-CSTN)integrates local spatial context,temporal evolution context and global correlation context into a unified architecture.At the same time,a multi-task learning is introduced to enable model to capture stronger inner-time pattern.In the label construction,we establish the hierarchical relationship between vertices according to the query frequencies.Then we propose a novel shortest path algorithm based on query frequency,called QHP algorithm.We conduct extensive performance studies on real datasets,which indicate that MT-CSTN is capable of outperforming the state-of-art baselines in terms of accuracy,and that the QHP algorithm is capable of outperforming the baselines in terms of efficiency.