A distributed shortest‐paths algorithm with distance‐dependent message complexities
Kouji Miura, Toshimitsu Masuzawa, Nobuki Tokura · Systems and Computers in Japan · 1994
Abstract This paper presents a distributed algorithm for the single‐source shortest‐paths problem in a network with nonnegative integral link weights. Its message complexity is , where n is the number of processors, e is the number of links, and D is the maximum distance from the root. The known shortest‐paths algorithm with the distance‐dependent message complexity requires O(min(Dn + e, n2)) messages. The algorithm of this paper is more efficient for networks with D = o(n3/e) and D = ω(e/n). Moreover, the breadth‐first search tree problem is considered.