最短路径图形结构算法及应用

Algorithm and application of shortest path graph structureAbstract Daily travelers rely on maps and navigation to query routes,calculate the shortestdistance between the two places,and choose the most suitable path.At this time,the demand of theshortest path algorithm is reflected.Dijkstra algorithm is the classic shortest path algorithm.It adopts the idea of breadth search(BFS),and depth first search(DFS)only considers the residual cost with the target point,so it often fails tofind the shortest path.As an extension of Dijkstra algorithm,A algorithm is widely used in pathfinding and graph traversal due to its high efficiency,and the final path is often the optimal solution.This paper mainly discusses the operation mode of A algorithm,uses Java code to writecorresponding programs,and demonstrates the operation of real life examples.It is found that themain reasons that affect the efficiency of algorithm search are the number of traversal of openlistnode and the total number of searches executed.The increase of traversal times and search timeswill lead to the increase of search timeAfter analyzing and improving the algorithm,the paper puts forward some improved schemes,suchas increasing the weight g of turning to reduce turning,replacing high precision grid with low precisiongrid,replacing grid with node grid.In some cases,the efficiency of the algorithm can be improved andthe accuracy loss can be ignored.Key words path planning shortest path A*algorithm operation efficiency