An algorithm of Shortest Path for Dynamic Situation and Its Simulation
Jianying Wang · Jisuanji fangzhen · 2007
Finding the shortest path through a graph is applied in many domains, including GIS, route planning for a robot, and computer network. It has made great progress in several decades. There are some popular algorithms of the shortest path, such as Dijkstra and A* algorithm. However these algorithms assume working in static environment and with complete accurate information, whereas in real life, the information is not always ideal, and situation often changes from time to time. When the situation changes, the entire path needs to be modified, thus lowering the speed. This paper introduces a new dynamic algorithm, which establishes an initial path. When the condition changes, it only computes part of the nodes locally, reduces the computing work. It can be concluded from the simulation that the more nodes in the graph, the more efficient the dynamic algorithm can be.