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

摘要：

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

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

所属期刊栏目：26

分类号：TP393.03(计算技术、计算机技术)

资助基金：国家社会科学基金军事学资助项目15GJ003-184;国家自然科学基金资助项目61271152

在线出版日期：2018-11-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：143-146