适用于无向网络的动态Dijkstra算法优化

Dynamic Dijkstra Algorithm for Undirected Networks

摘要:

网络拓扑发生变化时,利用静态Dijkstra算法重新计算最短路径树(SPT)会造成冗余计算。动态Dijkstra算法解决了这个问题,但目前动态算法一般是基于有向网络模型进行的研究。在已有的动态Dijkstra算法基础上,提出适用于无向网络的动态Dijkstra算法。算法主要解决了在无向网络中如何确定待更新节点的问题,对网络中的一条边权值增大、减小的处理方法进行了详细描述,并对已有的算法的筛选机制进行了优化。为了验证算法的正确性,用仿真实验实现了该算法并与静态算法进行性能比较。实验结果表明,新算法更能提高节点更新的时间效率。

关键词:路由算法;Dijkstra算法;无向网络;最短路径树;动态更新

Abstract:

Using the static Dijkstra algorithm to recalculate the shortest path tree (SPT) will cause redundant computation when the network topology changes. In order to reduce the computational complexity, a dynamic Dijkstra algorithm for undirected networks is proposed based on the existing dynamic Dijkstra algorithm. The problem of how to determine the nodes to be updated in the undirected network is solved. The algorithm describes the processing method of the increase and decrease of the weight. And the existing algorithms are optimized. In order to verify the correctness of the algorithm, which is implemented by code and compared with its static algorithm. Experimental results show that the new algorithm has more performance.

Key words:routing algorithm; Dijkstra algorithm; undirected network; shortest path tree; dynamic update