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

Volume

1

fYear

2001

fDate

2001

Firstpage

387

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;

fLanguage

English

Publisher

ieee

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

Type

conf

DOI

10.1109/ICII.2001.982778

Filename

982778