A Randomized Parallel Algorithm for Single-Source Shortest Paths
A Randomized Parallel Algorithm for Single-Source Shortest Paths
复制标题
单源最短路径的随机并行算法
DOI：
10.1006/jagm.1997.0888
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
Sairam Subramanian
中科院分区：
文献类型：
--
作者：
P. Klein;Sairam Subramanian
我们给出了一种随机并行算法来计算加权有向图中的单源最短路径。我们证明，精确的最短路径问题可以有效地简化为解决一系列近似最短路径子问题。我们的近似最短路径问题算法基于 Ullman 和 Yannakakis 在广度优先搜索并行算法中使用的技术。
We give a randomized parallel algorithm for computing single-source shortest paths in weighted digraphs. We show that the exact shortest-path problem can be efficiently reduced to solving a series of approximate shortest-path subproblems. Our algorithm for the approximate shortest-path problem is based on the technique used by Ullman and Yannakakis in a parallel algorithm for breadth-first search.