Improvement of A~* algorithm and its application in shortest path problem in dynamic networks
Jianmin Xu · JOURNAL OF SHENZHEN UNIVERSITY SCIENCE AND ENGINEERING · 2007
Efficient dynamic shortest path algorithm in static networks plays an important role in intelligent transpor-taitro syslem (ITS). To solve this problem, this paper brings forward dynamic A * algorithm based on the dynamic form of consistency assumption. It is proved that dynamic A * algorithm can solve one origin node to one destination node shortest paths problem in dynamic networks that satisfy first-in-first-out principle, if the dynamic lower boundary of the dynamic A * algorithm satisfies the dynamic form of consistency assumption, principle Finally the developed algorithms are implemented with a random dynamic network based on Guangzhou transportation network and their computational performance is analyzed through experiments. The test results showed that A* algorithm and Dijkstra algorithm's average computation time in solving the one-to-one shortest path problem in dynamic networks are 1. 43 and 6. 55 times than dynamic A * algorithm's.