The replicated data algorithm for solving the single source shortest path problem
J.A. Yang, D.C. Zhang · 2002
Proposes a data-parallel algorithm and a replicated data algorithm for the graph-theoretic operation of computing single-source shortest paths, and demonstrates the generality of the data replication technique by applying it to such a problem; then computes and discusses the speedup of the replicated data algorithm over the data-parallel algorithm; and, finally, points out that the data replication technique is not only applicable to fast image analysis, but is also general enough to be applicable to a large class of graph-theoretic operation problems.>