Research of Improved Shortest Path Algorithm in Campus GIS

ABSTRACT

In searching of campus geographic information system, the shortest path is always the key and its efficiency which determines the quality of the service of the digital campus directly. In the classic algorithm, the time complexity is proportional to the vertex number's square. With the increasing of the vertex number, the speed will fell down sharply. Based on the reality such as the large number of population, plenty of buildings, teaching resources, this article proposed an improved bi-directional A* algorithm which changing the target point into surface in search direction by using the middle list searching the target bi-directionally. The experimental results show that, compared with Dijkstra and A* algorithm, bi-directional A* algorithm is the fastest in the search, even when the vertex number large, it also can compute well.

Keywords: