Institute of Information Theories and Applications FOI ITHEA
Abstract:
In this paper the network problem of determining all-pairs shortest-path is examined. A distributed
algorithm which runs in O(n) time on a network of n nodes is presented. The number of messages of the
algorithm is O(e+n log n) where e is the number of communication links of the network. We prove that this
algorithm is time optimal.
