最短路径树的计算与修改算法

被引：2

作者：

马军，马绍汉

不详

机构：

[1] 山东大学计算机系

来源：

计算机研究与发展 | 1995年 / 12期

关键词：

图算法，最短路径树，修改算法;

D O I：

暂无

中图分类号：

O157.5 [图论];

学科分类号：

070104 ;

摘要：

在有向赋权图Ｇ＝（Ｖ，Ｅ，ＣＯＳＴ）上，给出了求解以每个顶点为根的向前／向后最短路径树（ＦＢＳＰＴ）算法。当Ｇ中的边被删除或边权增加时，证明了在这种情况下，不可能存在高效的对ＦＢＳＰＴ的修改算法；而对边添加和边权减少的情况，本文给出时间复杂性为Ｏ（ｎ￣２）的修改算法。此外，本文也讨论了对上述算法的并行实现问题。

引用

页码：45 / 49

页数：5