TY - JOUR

T1 - The quickest path problem

AU - Chen, Y. L.

AU - Chin, Y. H.

PY - 1990

Y1 - 1990

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=0025228171&partnerID=8YFLogxK

U2 - 10.1016/0305-0548(90)90039-A

DO - 10.1016/0305-0548(90)90039-A

M3 - 期刊論文

AN - SCOPUS:0025228171

VL - 17

SP - 153

EP - 161

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

IS - 2

ER -