Efficient Computation Of Shortest Path Distances In Road Networks Based On Neural Networks

In the field of computer science,a graph is a classical data structure used to represent dependencies between nodes.A road network,or a traffic network,is a typical graph data in which each road represents an edge on the graph and each intersection represents a vertex on the graph.The shortest path distance on a road network refers to the length of the shortest path between any two points on the road network.Computing the shortest path distance on a road network is a core operation for many location-based services(LBS).Traditional exact methods for computing the shortest path distance,such as Dijkstra and Astar,suffer from high time complexity and low efficiency when dealing with massive data and user queries.Therefore,this paper proposes a learning-based approach for approximating the shortest path distance on the road network.By sacrificing a certain level of computational accuracy,the proposed method achieves a comprehensive improvement in both time and space efficiency.Furthermore,this paper proposes to use Geohash encoding as a feature representation of nodes,which can characterize the spatial position information of nodes and is closely related to distance prediction tasks.Compared with other embedding methods,Geohash encoding has the advantages of high information density,high information quality,and ease of neural network training.Using this encoding can significantly simplify the model structure,reduce the cost of model training,and reduce the complexity of storing and calculating the shortest path distance using the model.Specifically,the trained model only requires constant storage cost.The representation of each node is also reduced to 9 digits of Base32 characters,i.e.,45 digits of0,1 encoding.After the model is trained,it can return results in constant time.Secondly,Geohash encoding is a type of space-filling curve,Z-curve and has some discontinuity.Although in most cases,this encoding can represent the spatial position information of nodes well,for some cases,neighbor information is required as a supplement to achieve noise reduction and data enhancement.This paper implements the convolution operation in graph neural networks to achieve this effect and further uses the attention mechanism to adaptively adjust the weight information of neighboring nodes to enhance the flexibility of the model.Compared with the method based on multi-layer perceptron,this method can better utilize the topological information in the graph structure.Finally,the experiment found that the model’s training performance varied significantly with different data scales.To address this issue,this paper proposes to use methods such as logarithmic normalization and square root normalization to scale the data to the same level,reduce the numerical differences in the normalized data,enhance the model’s robustness,and enable the model to perform well on data at different scales.The experimental results demonstrate that the model proposed in this paper has certain advantages over other methods in terms of time efficiency,space efficiency,and computational accuracy.To be more specific,after completing the training process,the model can return user queries in constant time complexity(i.e.,(1)),while the model and node representations require storage space proportional to the number of vertices(i.e.,((1)).Additionally,there is only a minimal amount of precision loss.