路径节点驱动的低代价最短路径树算法

摘要

Dijkstra算法是一个优秀的最短路径求解算法,同时也产生一棵最短路径树SPT(shortest path tree);该算法在网络计算与优化中得到了广泛的应用.为了对最短路径树进行代价优化,提出了路径节点驱动的思想.基于这种思想设计了路径节点驱动的最低代价最短路径树算法LCSPT(least-cost shortest path tree algorithm).通过LCSPT算法一个正计算节点能够最大化与当前最短路径树中的路径共享,因而进一步优化SPT树代价性能,生成高性能的SPT树.作为算法的重要组成部分,使用数学归纳法证明了算法的正确性;从理论上分析了LCSPT算法的代价性能,以及和同类算法相比如何取得最小代价性能;同时,对其时间复杂度和空间复杂度进行了分析.最后通过3个仿真实验验证了该算法在构建SPT时的正确性和其最小代价最短路径树特性.%Dijkstra algorithm is an excellent shortest path algorithm, which can compute a shortest path between two given nodes and also gain a shortest path tree (SPT) from a source to some destination nodes. It has been widely applied in many aspects of network computing. In order to optimize the cost performance of SPT, a path nodes-driven idea is introduced which derives from the destination nodes-driven idea. By using the idea, an algorithm called least-cost shortest path tree (LCSPT) is designed. To describe LCSPT algorithm in detail, its main running steps and the pseudo codes are introduced. Through LCSPT algorithm, a computing node can share links with path nodes which have belonged to the existing shortest path tree, and so a high-performance least-cost SPT can be constructed. As an important component of LCSPT, its correctness is proofed by mathematical induction, and the cost performance of LCSPT is analyzed in theories. Moreover, the time complex and the space complex are computed and compared with the other SPT algorithms. At last, three simulation experiments are done and the resulted data show that LCSPT algorithm not only produces a SPT tree correctly but also has the best cost performance among all the shortest path tree algorithms.