Shortest path computation is required by a large number of applications such as VLSI,
transportation, and communication networks. These applications, which are often very
complex and have sparse networks, generally use parallel labeling shortest path algorithms.
Such algorithms, when implemented on a distributed memory machine, require termination
detection methods; these methods consist of some type of synchronization among all
processors. Because global synchronization can be costly, it is assumed that the best …