Rosen, J. B.; Sun, S.-Z.; Xue, G.-L. Algorithms for the quickest path problem and the enumeration of quickest paths. (English) Zbl 0747.90104 Comput. Oper. Res. 18, No. 6, 579-584 (1991). Summary: Let \(N=(V,A,c,\ell)\) be an input network with node set \(V\), arc set \(A\), positive are weight function \(c\) and nonnegative arc weight function \(\ell\). Let \(\sigma\) be the amount of data to be transmitted. The quickset path problem is to find a routing path in \(N\) to transmit the given amount of data in minimum time. In a recent paper, Y. L. Chen and Y. H. Chin [ibid. 17, No. 2, 153-161 (1990; Zbl 0698.90083)] proposed this problem and developed algorithms for the single pair quickest path problem with time complexity \(O(re+rn \log n)\), where \(n=| V|\), \(e=| A|\), and \(r\) is the number of distinct capacity values of \(N\).In this paper, we first develop an alternative algorithm for the single pair quickest path problem with the same time complexity and less space requirement. We then study the constrained quickest path problem and propose an \(O(re+rn \log n)\) time algorithm. Finally, we develop an algorithm to enumerate the first \(m\) quickest paths to send a given amount of data from one node to another with time complexity \(O(rmne+rmn^ 2\log n)\). Cited in 2 ReviewsCited in 40 Documents MSC: 90C35 Programming involving graphs or networks 90C60 Abstract computational complexity for mathematical programming problems 90B18 Communication networks in operations research 90-08 Computational methods for problems pertaining to operations research and mathematical programming Keywords:input network; routing path; minimum time; single pair quickest path problem Citations:Zbl 0698.90083 PDFBibTeX XMLCite \textit{J. B. Rosen} et al., Comput. Oper. Res. 18, No. 6, 579--584 (1991; Zbl 0747.90104) Full Text: DOI References: [1] Ahuja, R. K., Minimum cost-reliability ratio problem, Computers Ops Res., 15, 83-89 (1988) · Zbl 0643.90088 [2] Bodin, L. D.; Golden, B. L.; Assad, A. A.; Ball, M. O., Routing and scheduling of vehicles and crews: the state of the art, Computers Ops Res., 10, 63-211 (1983) [3] Chen, Y. L.; Chin, Y. H., The quickest path problem, Computers Ops Res., 17, 153-161 (1990) · Zbl 0698.90083 [4] Fredman, M. L.; Tarjan, R. E., Fibonacci heaps and their uses in improved network optimization algorithms, J. Ass. Comput. Math., 34, 596-615 (1987) · Zbl 1412.68048 [5] Horowitz, E.; Sahni, S., Fundamentals of Data Structures in Pascal (1987), Computer Science Press: Computer Science Press New York [6] Pierce, A. R., Bibliography on algorithms for shortest path, shortest spanning tree, and related circuit routing problems, Networks, 5, 129-149 (1975) · Zbl 0307.90078 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.