A label-setting algorithm for finding a quickest path

A label-setting algorithm for finding a quickest path

0.00 Avg rating0 Votes
Article ID: iaor2005717
Country: United Kingdom
Volume: 31
Issue: 14
Start Page Number: 2405
End Page Number: 2418
Publication Date: Dec 2004
Journal: Computers and Operations Research
Authors: , ,
Abstract:

The quickest path problem is to find a path to send a given amount of data from the source to the destination with minimum transmission time. To find the quickest path, existing algorithms enumerate non-dominated paths with distinct capacity, and then determine a quickest path by comparing their transmission time. In this paper, we propose a label-setting algorithm for finding a quickest path by transforming a network to another network where an important property holds that each subpath of a quickest path is also a quickest path. The proposed algorithm avoids enumerating non-dominated paths whose transmission time is greater than the minimum transmission time. Although the computational complexity of the proposed algorithm is the same as that of existing algorithms, experimental results show that our algorithm is efficient when a network has two or more non-dominated paths.

Reviews

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