Shortest Path Algorithms:Taxonomy and Advance in Research
Feng Gui Lu · 2001
The shortest path problem is a research topic in the field of geographic information science and computer science. In this paper, the author discussed the taxonomy of the shortest path algorithms from problem type, network characteristics and solution techniques, compared the time complexities of those common used sequential shortest path algorithms and evaluated the relevant researches. The most popular sequential shortest path algorithms are evaluated for their practical efficiency with urban traffic networks. The advance of time dependant and parallel shortest path algorithms is also discussed.