| 摘要: |
| 本文首先提出求解SSSP问题图运算的数据并行算法及复制数据算法，并把复制数据技术成功地用于求解SSSP问题图运算证明算法的有效性，然后计算并讨论复制数据算法对数据并行算法的加速，最后指出复制数据技术不仅能用于图象的快速分析，而且也能广泛地用于解各种图运算问题． |
| 关键词: SSSP问题，复制数据算法，数据并行算法，横向优先搜索算法，加速比． |
| DOI： |
| 分类号: |
| 基金项目: |
|
| A STUDY ON THE REPLlCATED DATA ALGORITHM FOR SOLVING THE SINGLE SOURCE SHORTEST PATH PROBLEM |
|
Yang Jing'an
|
| Abstract: |
| This paper first proposes a data parallel algorithm and a replicated data algo-rithm for the graph theoretic operation of computing the single source shortest paths and demonstrates the generality of the data replicated technique by applying it to the graph theoretic operation for solving SSSP problems，then computes and discusses the speedup of the replicated data algorithm over the data parallel algorithm，finally points out that the data replication technique is not only applicable to fast image analysis，hut also is general enouth to be applicable to a large class of the graph theoretic operation problems． |
| Key words: SSSP problems,the replicated data algorithm,data parallel algorithm,breadth—first—search—algorithm,speedup ratio． |
