Path Nodes-Driven Least-Cost Shortest Path Tree Algorithm

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.