This paper considers the problem reconstructing the shortest path, act is, the problem to reconstruct the weighted shortest path in reponses to topology change of the network. This paper proposes a distributed algorithm that reconstructs the weighted ...
This paper considers the problem reconstructing the shortest path, act is, the problem to reconstruct the weighted shortest path in reponses to topology change of the network. This paper proposes a distributed algorithm that reconstructs the weighted shortest path after several processors and links are added and deleted. Its message complexity and ideal-time complexity are O(u^(2) + a + n′), where n′ is the number of processors in the network after the topology change, a is the number of added links, and u is the total number of processors in the biconnected component (of the network before the topology change) including the deleted links or added links.