点击次数：

论文类型：会议论文

发表时间：2005-05-22

收录刊物：EI

卷号：3516 LNCS

期号：III

页面范围：975-978

摘要：This paper presents the Optimality Theorem in distributed parallel environment. Based on this theorem, a parallel algorithm using network-tree model is presented to compute shortest paths in large-scale networks. The correctness of this algorithm is proved theoretically and a series of computational test problems are performed on PC cluster. Factors such as network size and level of the network, which take effect on the performance, are discussed in detail. Results of the experiments show that the proposed parallel algorithm is efficient in computing shortest paths in large-scale networks, especially when the network size is great. © Springer-Verlag Berlin Heidelberg 2005.