TY - JOUR
T1 - Finding the k quickest simple paths in a network
AU - Chen, Y. L.
PY - 1994/4/22
Y1 - 1994/4/22
N2 - Let N be a network with n nodes and m arcs, and let σ 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. The problem considered in this paper is to find the first k quickest simple paths for a given pair of nodes, and an algorithm is designed. The complexity required by the proposed algorithm is O(kmn3 + kmn log k) if the network is directed and is O(kmn2 + kmn log k) if the network is undirected.
AB - Let N be a network with n nodes and m arcs, and let σ 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. The problem considered in this paper is to find the first k quickest simple paths for a given pair of nodes, and an algorithm is designed. The complexity required by the proposed algorithm is O(kmn3 + kmn log k) if the network is directed and is O(kmn2 + kmn log k) if the network is undirected.
KW - Combinatorial problems
KW - Design of algorithms
KW - Shortest and quickest path
UR - http://www.scopus.com/inward/record.url?scp=0028416914&partnerID=8YFLogxK
U2 - 10.1016/0020-0190(94)00008-5
DO - 10.1016/0020-0190(94)00008-5
M3 - 期刊論文
AN - SCOPUS:0028416914
SN - 0020-0190
VL - 50
SP - 89
EP - 92
JO - Information Processing Letters
JF - Information Processing Letters
IS - 2
ER -