Design Of Urban Traffic Network Shortest Path Algorithm Based On Big Data Analysis

The shortest path problem is one of the classic and basic problem in graph theory,after more than half a century of research,it attention by a large amount of researchers in wide range of areas,the research results of the shortest path algorithm are also remarkable.The shortest path problem is widely used in a variety of realistic scenarios,one of the basic research contents of the shortest path problem is to select the optimal travel path in the traffic network.With the development of the city,the scale of urban transportation network is gradually expanding,the number of network nodes is complex and diverse.AS a result,the classic shortest path algorithm no longer applies.Therefore,the optimization techniques and optimization algorithms of various shortest paths applied to large-scale networks have become the focus of the shortest path algorithm research in recent years.In these studies,the parallel computing algorithm and the preprocessing to obtain the auxiliary data to optimize the shortest path calculation become the trend of the algorithm research.In recent years,a series of the shortest path algorithms which is suitable for large-scale network and dynamic network are put forward by domestic and foreign scholars.Most of the algorithm using a heuristic path search mode,parallel computing mode or use network layered model to calculate,this kind of algorithm are suited for large-scale network computing.In this paper,we summarize the relevant experience in studying the existing research results and combines parallel computing and heuristic search,we propose a multi-source shortest path algorithm which is suitable for large-scale transportation network.This algorithm is mainly divided into three parts which including data preprocessing,shortest path calculation of the same subgraph and shortest path calculation between multiple subgraphs.In data preprocessing,we designed a graph decomposition method.The number of nodes affects the efficiency of the algorithm,then our algorithm divide the original network and construct a two-layer abstract network.When the starting node and the destination node belong to one subgraph,we designed PFloyd algorithm which is calculate in parallel.It is proved by experiment that the PFloyd algorithm is suitable for the shortest path calculation of the subgraph with more than thousands numbers of nodes.When the starting node and destination node belong to two different subgraphs,we design the SPS algorithm.The SPS algorithm is based on the abstract two-layer network obtained after the graph decomposition strategy.The calculation method of the distance between the subgraphsis defined,and the subgraph which is most likely to pass through the shortest path is selected to narrow the search scope of the algorithm.We choose the San Francisco bay area transportation network as the experimental data and three parts of the algorithm are tested respectively.For PFloyd algorithm and SPS algorithm,we conducted a comparative experiment respectively.The experiment proves that the shortest path algorithm in this paper has good performance in the shortest path calculation.