A New Algorithm for Finding Shortcut in a City's Road Net Based on GIS Technology
Han Yan · Chinese Journal of Computers · 2000
This article discusses a new algorithm which gets the shortest path between two points in a city's road net. This algorithm is based on the geographic relevance relationship among roads in the road net. The presented algorithm's complexity is just proportion to the number of nodes in the road net while conventional shortcut algorithm's complexity is proportion to the power of the number of nodes. At the end of the article, it provides some instance which prove that the algorithm is applied and reliable.