Application and simulation of improved Dijksta algorithm in a vehicle navigation system
Bo Zhang · Applied science and technology · 2011
Vehicle navigation is one of the important applications of the single-source single-target shortest path algorithm.As a basic function of the vehicle navigation system,the shortest route algorithm has been a research hot topic in vehicle navigation field.This application frequently involves large scale networks with limited computing power and memory space.Because of real time requirement of the practical system,it is necessary to optimize Dijkstra algorithm-a typical single-source shortest route algorithm.Based on the analysis of the temporal complicacy and spatial complicacy of Dijkstra algorithm,this paper presents a novel improved Dijkstra algorithm,which can run much more efficiently compared with original algorithm.According to Dijkstra algorithms,the improved algorithm is used to reduce searching space and binary heap data structure is used to complete the operation of priority queue.Firstly,this paper adopts the adjacency list as store structure of topology of road network.Secondly,binary heap is used to implement the operation of priority queue.Thirdly,search course is divided into several phrases according to the special spatial distribution of nodes.A search mechanism of dynamically restricting the search areas in stages is introduced,which can gradually reduce search areas and greatly decrease the search data volume of the algorithm.Finally,the tests in real road network prove that the modified algorithm is workable and time-saving.