An algorithm for finding the \(k\) quickest paths in a network
type: Item
instance of: scholarly article
title: An algorithm for finding the \(k\) quickest paths in a network
zbMATH Open document ID: 0773.90081
DOI: 10.1016/0305-0548(93)90096-2
author: S. Singh
published in: Computers \& Operations Research
publication date: 1993-01-17T00:00:00Z
review text: The traditional shortest path problem is to find a shortest path from the source node \(s\) to the sink node \(t\) in a network where each arc has only one attribute ``distance'' associated with it. Although this is a useful model to solve many practical problems, there are situations where this model is inappropriate because each arc of the network has multiple attributes. For example, in a communication network, the transmission time between two connected nodes depends on not only the distance but also the capacity. Therefore, the author and \textit{Y. H. Chin} [Comput. Oper. Res. 17, No. 2, 153-161 (1990; Zbl 0698.90083)] defined the quickest path as a problem of finding a minimum transmission time path from node \(s\) to node \(t\) in a network where each arc has two attributes, one is the lead time and the other is the capacity. In this paper, the author further extends the quickest path problem such that the first \(k\) quickest looping paths are enumerated instead of simply a single quickest path. Let \(n\) and \(m\) denote the numbers of nodes and arcs in the network. Then the algorithm proposed in this paper has time complexity of \(O(m^ 2+(m+k)n \log n+k^{1.5} \log k)\). If \(O(k)=O(m)\), then the proposed algorithm can be run in time of \(O(m^ 2+mn \log n)\), which is identical to the time required by the most efficient algorithm to find a single quickest path. In other words, if \(O(k)\leq O(m)\), then our algorithm for finding the first \(k\) quickest paths is as efficient as the best known algorithm for finding a single quickest path.
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 98586
zbMATH Keywords: shortest path
zbMATH Keywords: multiple attributes
zbMATH Keywords: quickest path
zbMATH Keywords: minimum transmission time path
MaRDI profile type: Publication
full work available at URL: 0305-0548(93)90096-2
OpenAlex ID: W2014156227
cites work: The quickest path problem
cites work: Shortest-path algorithms: Taxonomy and annotation
cites work: Algorithms for the quickest path problem and the enumeration of quickest paths
cites work: An efficient algorithm for K shortest simple paths
cites work: Finding the K Shortest Loopless Paths in a Network
cites work: Data Structures and Computer Science Techniques in Operations Research
cites work: On algorithms for finding the k shortest paths in a network
cites work: Fibonacci heaps and their uses in improved network optimization algorithms
cites work: Q4130999
cites work: An Appraisal of Some Shortest-Path Algorithms
description: scientific article; zbMATH DE number 98586