A Distributed Algorithm for Weighted Shortest Path Problem


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 6, No. 1, pp. 42-48, Jan. 1999
10.3745/KIPSTE.1999.6.1.42,   PDF Download:

Abstract

Consider the situation that informations necessary to solve a certain problem are distributed among processors on a network. It is called a distributed algorithm that in this situation each processor exchanges the message with adjacent processors to solve the problem. This paper proposes a distributed algorithm to solve the problem that constructs the weighted shortest path tree in an asynchronous network system. In general, a distributed algorithm is estimated by the number of messages(message complexity) and the number of unit complexity(ideal time complexity). Message complexity and ideal-time complexity of the distributed algorithm proposed in this paper are O(n5/3) and O(n%u221An) respectively, where n is the number of processors on the network.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
P. J. Ho and P. Y. Young, "A Distributed Algorithm for Weighted Shortest Path Problem," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 6, no. 1, pp. 42-48, 1999. DOI: 10.3745/KIPSTE.1999.6.1.42.

[ACM Style]
Park Jung Ho and Park Yoon Young. 1999. A Distributed Algorithm for Weighted Shortest Path Problem. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 6, 1, (1999), 42-48. DOI: 10.3745/KIPSTE.1999.6.1.42.