基于有序双循环链表的低代价最短路径树快速算法

Fast low-cost shortest path tree algorithm based on ordinal circularly double linked list

低代价最短路径树是一种广泛使用的多播树。在FLSPT算法的基础上,通过选择有序双循环链表作为待发展节点序列Q的运算与存储中心,提出了基于有序双循环链表的低代价最短路径树快速算法DKFLSPT。该算法构造的最短路径树与FLSPT算法构造的最短路径树具有相同的性能,利用有序双循环链表的局部性原理来达到改进节点路径最小值的搜索过程。随机网络模型的仿真结果表明,DKFLSPT算法效率平均可以提高19%。

Low-cost shortest path tree is a commonly-used multicast tree type. On the foundation of the Fast Low-cost Shortest Path Tree （FLSPT） algorithm, the ordinal circularly linked list was selected as the calculating and saving center of sequence Q of nodes which were waiting for development. The fast low-cost shortest path tree algorithm based on ordinal circularly double linked list named Fast Low-cost Shortest Path Tree （DKFLSPT） was put forward. The shortest path tree constructed by DKFLSPT algorithm is the same as that constructed by FLSPT algorithm, making use of the part principle of ordinal circ^arly double linked list to improve the search procedure which can get the shortest path of nodes. The imitated experiment of random network indicates that the efficiency of DKFLSPT algorithm can be raised by 19%.