Title :
Improvement of Dijkstra´s algorithm and its application in route planning
Author :
Fan, DongKai ; Shi, Ping
Author_Institution :
Sch. of Transp. & Vehicle Eng., Shandong Univ. of Technol., Zibo, China
Abstract :
In order to improve the efficiency of road network route planning,many experts and scholars have conducted some studies, Dijkstra´s algorithm is a research hotspot. The Dijkstra´s algorithm has its own shortcomings when seeking an optimal path between two points, but it has irreplaceable advantages. Through the analysis of strengths and weaknesses of the classic Dijkstra´s algorithm, we can find that the main drawbacks can be summarized as two points: storage structure and searching area. Therefore, the paper has improved these two points, namely the improvement of data storage structure and the searching area of restricted algorithms. And its validity is obtained by analyzing the experimental results.
Keywords :
data structures; network theory (graphs); search problems; storage management; transportation; Dijkstra algorithm; data storage structure; restricted algorithm; road network route planning; searching area; Algorithm design and analysis; Approximation algorithms; Arrays; Complexity theory; Planning; Roads; Vehicles; Dijkstra´s algorithm; restricted searching area; road network; route planning; storage structure;
Conference_Titel :
Fuzzy Systems and Knowledge Discovery (FSKD), 2010 Seventh International Conference on
Conference_Location :
Yantai, Shandong
Print_ISBN :
978-1-4244-5931-5
DOI :
10.1109/FSKD.2010.5569452