Dual algorithms for the shortest path tree problem

Dual algorithms for the shortest path tree problem

0.00 Avg rating0 Votes
Article ID: iaor2002409
Country: United States
Volume: 29
Issue: 2
Start Page Number: 125
End Page Number: 133
Publication Date: Mar 1997
Journal: Networks
Authors: ,
Keywords: duality
Abstract:

We consider dual approaches for the Shortest Path Tree problem. After a brief introduction to the problem, we review the most important dual algorithms which have been described in the literature for its solution and propose a new family of dual ascent algorithms. In these algorithms, local and global dual updating operations are performed at the nodes in order to enlarge a partial shortest path tree, which at the beginning contains only the root node, until a shortest path tree is found. Several kinds of dual updating operations are proposed, which allow one to derive different dual algorithms from a general schema. One of them, in particular, which is based only on global operations, can be viewed as a dual interpretation of Dijkstra's classical algorithm. Due to their structure, all the proposed algorithms are suitable for parallel implementation. They are also suitable for reoptimization approaches, when the computation of shortest paths from different root nodes is required.

Reviews

Required fields are marked *. Your email address will not be published.