Research and Realization of Kth Path Planning Algorithm under Large-Scale Data Which Meets the Requirement for Repeatability

Path planning problem is one of the key contents in the research field of Geographic Information System (GIS), among which the finding of the shortest path is always a hot topic. When there is large quantity of data, the efficiency of traditional algorithms of Kth shortest paths is relatively low, and some path problems concerning big difference between the planned Kth paths under actual requirements cannot be solved. On the basis of Dijkstra algorithm, the concepts of favorability and repeatability are introduced to find Kth paths including the shortest in the current graph cyclically by determination of repeatability of path results and the change of graph caused by the change of favorability, thereby realizing the planning of multiple different paths. Compared with similar algorithms, this algorithm is faster, and the multiple path results obtained meet the requirement for certain repeatability while the lengths of paths are also quite reasonable.