稳定的最短路径树及其构造算法

• 作者: 史雯隽 杨晓花 武继刚 赵国栋
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 最短路径树 动态网络 重新构建 稳定的
• 年，卷（期）: 2016,（3）
• 所属期刊栏目: 高性能计算
• 页码范围: 418-424
• 页数: 7页
• 分类号: TP393
• 字数: 5866字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2016.03.003

摘要

构建最短路径树是动态网络研究的重要问题之一.在动态网络中,当边状态发生变化时会引发最短路径树动态的重新构建,反复地计算不仅消耗大量时间,也会导致最短路径树的频繁变化.提出一种稳定的最短路径树构造算法,使得构造的路径树在动态网络上更稳定,即更新最短路径树所需的操作数更少.该算法通过记录频繁变化的不稳定边并尽可能避免将其加入最短路径树中,从而能够高效地减少边变化带来的操作.实验结果表明,与传统的动态最短路径树算法相比,该算法可以得到更稳定的最短路径树,并且更新时间减少了57.24％,结点更新次数降低了43.6％.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	武继刚	天津工业大学计算机科学与软件学院	24	102	6.0	8.0
5	杨晓花	天津工业大学计算机科学与软件学院	1	6	1.0	1.0
9	史雯隽	天津工业大学计算机科学与软件学院	4	11	2.0	3.0