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.