In an execution of a distributed program, processes communicate among
themselves by exchanging messages. The execution speed of the program
could be expedited by a faster message delivery system, transmitting m
essages to their destinations through their respective shortest paths.
Some distributed algorithms have been proposed in recent years for de
termining all pairs shortest paths for an arbitrary computer network.
The best known algorithm uses O(n(2)logn) messages, where n is the num
ber of computers in the network. This paper presents a new distributed
algorithm for the same problem using 2n(2) messages in the worst case
. This algorithm uses a strategy quite different from those of the oth
er algorithms for the same problem. (C) 1997 Academic Press.