Analysis And Research On Shortest Path Tree Algorithm In Dynamic Environment

In the practical applications and real life the shortest path problem plays a very important role, with the continuous development of sensor technology,communication technology and computer technology. As in the transport network, we need to find the best route so quickly reach the destination. In logistics, the logistics company not only to consider the speed but also consider the logistics costs of logistics, all these practical problems can be through modeling and eventually formalized as the shortest path problem, thus using classical algorithms to solve practical problems.In recent years, the shortest path tree problem has been widely studied, and has derived a lot of mature and stable static algorithm, however, with the changes of network size and network needs, these static algorithms have been unable to meet the needs of a dynamic network. The status will changed over time for dynamic network, in which the changed status will lead to reconstruct the shortest path tree dynamically, and repeated calculation not only consumes a lot of time, but also results in frequent changes of the shortest path tree, and eventually making the shortest path tree becomes extremely unstable.In this paper we proposed the concept of unstable edges based on the previous analysis algorithms, we analysis and statistics the unstable edges by recording frequently changing edges as much as possible to avoid them to add to shortest path tree, which can effectively reduce the number of the updating operations. Therefore, we proposed a stable shortest path tree algorithm in the dynamic network, which compared with the previous algorithms, it can construct the more stabler shortest path tree on a dynamic network, that is update the number of the updating operations less in the shortest path tree. To test the performance of the algorithm, we executed scientific experiments in a random network environment. Experimental results show that the presented algorithm can generate relatively stable shortest path tree, compared with traditional dynamic network shortest path tree algorithm. The update time is improved by 57.24%, the number of updating operations on nodes is reduced by 43.6%. In addition, it can be obtain the precision solution about approximately 60%of the experimental random examples, in the calculation the weights of the shortest path tree our algorithm will be a little error, but an error the entire solution can be controlled within 2%.