Implementing parallel shortest-paths algorithms
Marios C. Papaefthymiou, Joseph Rodrigue · DIMACS series in discrete mathematics and theoretical computer science · 1997
. We have implemented two parallel versions of the Bellman-FordMoore algorithm for the single-source shortest-paths problem. Our software is written in C and runs on the CM-5 parallel supercomputer using CMMD communication primitives. We have compared the performance of our parallel programs with a serial implementation of the Bellman-Ford-Moore algorithm developed by Cherkassky, Goldberg and Radzik. In our experiments we used 50 randomly generated graphs with up to 2 15 vertices and 2 21 edges. Our fastest parallel program always achieved speedups greater than 1 when the average degree of the graphs exceeded 2 5 for the smaller and 2 3 for the larger inputs in our test suite. On dense graphs, we achieved speedups of up to 7.8 on a CM-5 with 32 processors. 1. Introduction The shortest-paths problem is a classic combinatorial optimization problem that arises in a wide spectrum of applications including VLSI design, network routing, and commodity flow. Several serial and paralle...