Title :
Algorithm and its application of N shortest paths problem
Author :
Deng-feng, Chai ; Deng-rong, Zhang
Author_Institution :
Instn. of Space & Inf. Technol., Zhejiang Univ., Hangzhou, China
Abstract :
The shortest path problem is one of the basic and classical problems of graph theory and is applied to many fields, such as GIS network analysis. Dijkstra´s and Floyd´s algorithms are two classical algorithms. While the shortest path indicates only the shortest one path, algorithms designed for it can only get one path. This paper brings forward the N shortest paths problem then designs an algorithm for it and analyzes its complexity. The algorithm is tested by experiment and applied to a traffic consultation system of Guangzhou city and proved to be efficient
Keywords :
computational complexity; geographic information systems; graph theory; traffic engineering computing; Dijkstra algorithm; Floyd algorithm; GIS network analysis; Guangzhou city; N shortest paths problem; complexity; graph theory; traffic consultation system; Algorithm design and analysis; Cities and towns; Decision making; Geographic Information Systems; Graph theory; Information analysis; Information technology; Shortest path problem; Space technology; System testing;
Conference_Titel :
Info-tech and Info-net, 2001. Proceedings. ICII 2001 - Beijing. 2001 International Conferences on
Conference_Location :
Beijing
Print_ISBN :
0-7803-7010-4
DOI :
10.1109/ICII.2001.982778
