Title :
Research on the Algorithm for K-Shortest Paths Problem based on A* in Complicated Network
Author :
Chen, Lichao ; Liu, Jia ; Zhang, Yingjun ; Xie, Binhong
Author_Institution :
Taiyuan Univ. of Sci. & Technol., Taiyuan
Abstract :
Focusing on the optimization problems about complicated network, this paper presents an algorithm KSPA to solve the K-shortest paths problem in complicated network based on A* algorithm, in which the time cost is taken as target function and the establishment of the target function model is given. Experimental results show the proposed KSPA maintains an excellent efficiency on certain public traffic data. It can be used to solve the K-shortest paths problems in multi-graph.
Keywords :
graph theory; network theory (graphs); optimisation; road traffic; transportation; A* algorithm; K-shortest path problem; complicated network; multigraph; optimization; public traffic data; target function model; Computer science; Cost function; Data structures; Geography; Intelligent networks; Intelligent transportation systems; Roads; Shortest path problem; Telecommunication traffic; Traffic control; A* algorithm; K-shortest paths; multi;
Conference_Titel :
Cognitive Informatics, 6th IEEE International Conference on
Conference_Location :
Lake Tahoo, CA
Print_ISBN :
9781-4244-1327-0
Electronic_ISBN :
978-1-4244-1328-7
DOI :
10.1109/COGINF.2007.4341919
