The Statistic Characteristics And The Research Of Practical Algorithm For The Shortest Path In Urban Roads Network

Many studies on shortest-path algorithms have been conducted in fields of real-time navigation for automobile and emergency succor. The Dijkstra algorithms, classical and professional, are the academic basis of conducting to solve problems. As it has low conducted efficiency in urban roads network and may not meet the requirement of effective and real-time, many domestic and international scholars have made deep research on improving the algorithms.People researching on traditional optimized algorithms only realized abstract network topology in the process of design, striving for improving effectivity of the algorithms through updating computer data structure or operational research problems, which neglecting the existing spatial characteristics in specific roads network. With the development of WebGIS, Mobile GIS and GPS, dynamic path layout will be the trend of future improvement. It can be obtained information of real time roads condition, updating weight property of the path by Internet and then use the shortest-path algorithms to work it out. Instead, people who research on traditional optimized algorithms don't consider the affection of transmitting and updating data quantity on the performance of the whole algorithms. Therefore, the algorithms of controlling size of roads network can overcome the shortage of the traditional algorithms, which will enhance the effectivity of the shortest paths algorithms by combining other algorithms.New technology and methods is used for studying shortest path problem in this article. The ellipse model is designed by randomly taking out road nodes to calculate the shortest-path from the Shanghai roads network, observing the spatial distribution characteristic for stylebook, analyzing the statistic characteristics for the shortest-path. The model demarcated the range of searching the shortest-path algorithms within the ellipse. The ellipse model can improve the shortest-path algorithms, filtrating redundant nodes, reducing memory spending, decreasing calculated time, updating the weight of real time data transmission from the roads network and updating the performance and effectivity of algorithms. The area the improved shortest paths algorithm using the ellipse model searches is one-fifths of the classic Dijkstra algorithm.Based on random sample in Shanghai roads network, there is a linearity relation between the length of the shortest paths and the Euclidean distance and the Manhattan distance of the origin and destination in the analysis of the statistic characteristic for the...