An algorithm for finding the k quickest paths in a network

Research output: Contribution to journalArticlepeer-review

76 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 looping paths from the source to the sink, and an algorithm with time complexity of O(m2 + (m + k)n log n + k 3 2 log k) is developed.

Original languageEnglish
Pages (from-to)59-65
Number of pages7
JournalComputers and Operations Research
Volume20
Issue number1
DOIs
StatePublished - Jan 1993

Fingerprint

Dive into the research topics of 'An algorithm for finding the k quickest paths in a network'. Together they form a unique fingerprint.

Cite this