一种高效的最短路径树动态更新算法

被引：19

作者：

刘代波 ^{[1
]}

侯孟书 ^{[1
]}

武泽旭 ^{[2
]}

屈鸿 ^{[1
]}

机构：

[1] 电子科技大学计算机科学与工程学院

[2] 四川大学电气信息学院

来源：

计算机科学 | 2011年 / 38卷 / 07期

关键词：

动态计算; 最短路径树; 路由; 算法;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

080201 [机械制造及其自动化];

摘要：

计算动态环境下最短路径树是一个典型的组合优化问题。Ball-and-String模型是一种高效的动态更新算法,但仍存在不少冗余计算。针对Ball-and-String算法中边的处理进行了优化,从而提高了动态更新的效率,同时实现了对节点的删除和增加,以适应最短路径树的拓扑变化。实验结果表明新算法效率更高。

引用

收藏

页码：96 / 99

页数：4

相关论文

共 2 条

[1]

New dynamic SPT algorithm based on a ball-and-string model [J].

Narváez, P ;

Siu, KY ;

Tzeng, HY .

IEEE-ACM TRANSACTIONS ON NETWORKING, 2001, 9 (06) :706-718

[2]

A note on two problems in connexion with graphs..[J].E. W. Dijkstra.Numerische Mathematik.1959, 1