Finding the k quickest simple paths in a network

Y. L. Chen

doi:10.1016/0020-0190(94)00008-5

Finding the k quickest simple paths in a network

Y. L. Chen

Department of Information Management

Research output: Contribution to journal › Article › peer-review

85 Scopus citations

Abstract

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(kmn³ + kmn log k) if the network is directed and is O(kmn² + kmn log k) if the network is undirected.

Original language	English
Pages (from-to)	89-92
Number of pages	4
Journal	Information Processing Letters
Volume	50
Issue number	2
DOIs	https://doi.org/10.1016/0020-0190(94)00008-5
State	Published - 22 Apr 1994

Keywords

Combinatorial problems
Design of algorithms
Shortest and quickest path

Access to Document

10.1016/0020-0190(94)00008-5

Cite this

@article{55c557a8e62a43e4a53ab5dbe43eadba,

title = "Finding the k quickest simple paths in a network",

abstract = "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.",

keywords = "Combinatorial problems, Design of algorithms, Shortest and quickest path",

author = "Chen, {Y. L.}",

year = "1994",

month = apr,

day = "22",

doi = "10.1016/0020-0190(94)00008-5",

language = "???core.languages.en_GB???",

volume = "50",

pages = "89--92",

journal = "Information Processing Letters",

issn = "0020-0190",

number = "2",

}

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

VL - 50

SP - 89

EP - 92

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 2

ER -

Finding the k quickest simple paths in a network

Abstract

Keywords

Access to Document

Fingerprint

Cite this