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 -