Research On Shortest Path Query Algorithm With Negative Constraint On Road Network

The shortest path query problem in road network is to find the shortest distance path between two points in road network,which is one of the most basic problems in road network.At present,the research mainly focuses on the solution of general shortest path.However,in many practical applications,some specific intermediate points need to be avoided when the shortest path between two points is queried,which is called negative constraint later in this paper.For the shortest path query containing negative constraints,the existing shortest path query methods can not solve this problem,so it is necessary to design a shortest path algorithm for negative constraints.This paper studies this problem,and the specific research content is as follows.First,an online Algorithm DEVA(Dijkstra-based Except some Vertices Algorithm)is proposed for negating constraint shortest path query.Based on the idea of breadth-first traversal,three auxiliary arrays are maintained during the traversal to record the intermediate information of the paths meeting the conditions.The three arrays are vertex access array,distance array,and precursor vertex array.The vertex access array is used to mark whether the vertex is accessed,the distance array is used to record the shortest distance from the vertex to the source point,and the precursor vertex array is used to restore the shortest path.Based on the maintained information,DEVA algorithm can carry out negative-constrained shortest path query in a reasonable time.Secondly,an efficient index TDEVA(Tree Decomposition-based Except some Vertices Algorithm)for negating constraint shortest path query is proposed,and an algorithm for constructing this index is proposed.Based on the idea of tree decomposition,TDEVA index builds an index tree with multiple valid paths between vertices.Based on TDEVA index,it can deal with negative constraint shortest path query efficiently.Specifically,given the TDEVA index,query point and negative constraint conditions,the query algorithm proposed in this paper first finds the lowest common ancestor node w of source point s and target point t in the index tree,and processes the network vertex set from s and t to w in the index tree in a bottom-up order,so as to obtain the shortest path query results satisfying the conditions.On this basis,this paper proposes an optimization algorithm TDEVA* based on the combination of hierarchical traversal and parallel processing,which can further improve the query efficiency.Finally,the proposed algorithm is verified by experiments based on 7 real world road network data sets.Evaluation criteria include index establishment time and query time.The experimental results show that the online DEVA algorithm proposed in this paper can carry out the shortest path query with negative constraints within a reasonable time.Meanwhile,the query efficiency of the index-based TDEVA algorithm is significantly improved compared with the online DEVA algorithm,and TDEVA* further improves the query efficiency on the basis of TDEVA.