The quickest path problem

Y. L. Chen, Y. H. Chin

Research output: Contribution to journalArticlepeer-review

221 Scopus citations

Abstract

Let N be an input network and σ be the amount of data to be transmitted. The quickest path problem is to find a routing path in N such that the time required to ship σ units of data from the source to the sink is minimum. When the value of σ is given, an O(m2 + nm log m) algorithm is designed to find the quickest path, where m and n are the numbers of arcs and nodes in the network N, respectively. By generalizing this algorithm properly, a more general algorithm with similar time complexity is developed to find quickest paths for all possible values of σ. Using the algorithm, the values of σ can be divided into O(m) ordered regions such that each region has a corresponding quickest path; therefore, if the general algorithm is used as a preprocessing step to handle the input network N, then the problem of finding a quickest path for a given value of σ can be solved in time O(log m).

Original languageEnglish
Pages (from-to)153-161
Number of pages9
JournalComputers and Operations Research
Volume17
Issue number2
DOIs
StatePublished - 1990

Fingerprint

Dive into the research topics of 'The quickest path problem'. Together they form a unique fingerprint.

Cite this