×

Algorithms for the quickest path problem and the enumeration of quickest paths. (English) Zbl 0747.90104

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)\).

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

Citations:

Zbl 0698.90083
PDFBibTeX XMLCite
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.