Finding the k quickest simple paths in a network

Research output: Contribution to journalArticlepeer-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(kmn3 + kmn log k) if the network is directed and is O(kmn2 + kmn log k) if the network is undirected.

Original languageEnglish
Pages (from-to)89-92
Number of pages4
JournalInformation Processing Letters
Volume50
Issue number2
DOIs
StatePublished - 22 Apr 1994

Keywords

  • Combinatorial problems
  • Design of algorithms
  • Shortest and quickest path

Fingerprint

Dive into the research topics of 'Finding the k quickest simple paths in a network'. Together they form a unique fingerprint.

Cite this