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

THE ALGORITHMS FOR COMPUTING AND UPDATING THE SHORTEST TREES

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

The algorithms to compute the forward and backward shortest path tree (FBSPT)rooted at every vertex of a weighted directed graph G￣ (V,E,COST) are proposed. When the edges of G are deleted or the edge weights increase, it is shown that it is impossible to find an efficient incremental algorithm for FBSPT; For the case that new edges are added to G or edge weights decrease, an O(n2) incremental algorithm is given. In addition, the asynchronoUs parallel versions of the above algorithms are discussed also.