A DECOMPOSITION ALGORITHM FOR THE ALL-PAIRS SHORTEST-PATH PROBLEM ON MASSIVELY-PARALLEL COMPUTER ARCHITECTURES

Network optimization on parallel computer architectures has attracted significant interest in recent years. In this paper, we examine the so lution of the shortest path problem on massively parallel architecture s. We propose a network decomposition strategy that is amenable to par allel implementation and suggest efficient data structures and mapping s of the data to the processors that facilitate the solution of the pr oblem. We discuss computational results for the solution of networks o f various sizes on the Connection Machine CM-2(1) (a representative ma ssively parallel architecture) and compare the performance of the algo rithm to the performance of serial algorithms implemented on the CRAY X-MP2 supercomputer and VAXstation 3100.3 We also present an ''idealiz ed'' analysis of the algorithm and draw conclusions on properties of d ecomposition strategies that optimize its performance.