摘要
在有向赋权图G=(V,E,COST)上,给出了求解以每个顶点为根的向前/向后最短路径树(FBSPT)算法。当G中的边被删除或边权增加时,证明了在这种情况下,不可能存在高效的对FBSPT的修改算法;而对边添加和边权减少的情况,本文给出时间复杂性为O(n ̄2)的修改算法。此外,本文也讨论了对上述算法的并行实现问题。
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.
出处
《计算机研究与发展》
EI
CSCD
北大核心
1995年第12期45-49,共5页
Journal of Computer Research and Development
基金
国家自然科学基金
山东省自然科学基金
关键词
最短路径树
算法
有向图
图论
Graph algorithms. shone't path trees, incremental algorithms.