The week's pick
Reseach Article
Comprehensive Study on Computational Methods for K-Shortest Paths Problem
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 40 - Number 14 |
| Year of Publication: 2012 |
| Authors: Kalyan Mohanta |
10.5120/5048-7444
|
Kalyan Mohanta . Comprehensive Study on Computational Methods for K-Shortest Paths Problem. International Journal of Computer Applications. 40, 14 ( February 2012), 22-26. DOI=10.5120/5048-7444
Abstract
The application domains like network connection routing, highway and power line engineering, robot motion planning and other optimization problems require the computation of shortest path. Computations of K-shortest paths provide more (K-1) numbers of backup shortest paths for consideration, which enable the applicability of additional constraints on the particular domains. For instance, a biologist can determine the best of an alignment from the available instances of biological sequence alignments generated from more than one shortest paths computation. The purpose of this paper is to provide a comprehensive review of existing algorithms available for K-shortest paths computation. It will be useful for researcher to implement the effective K-shortest paths computation based on their matching computational requirements over the domain of their interest.
References
- Bock, F., Kantner, H. and Haynes, J. 1957 An Algorithm (The rh Best Path Algorithm) for Finding and Ranking Paths Through a Network, Research Report, Armour Research Foundation, Chicago, Illinois, November 15.
- Pollack, M. 1961 The k-th Best Route Through a Network, Operations Research, Vol. 9, No. 4, pp. 578-580.
- Clarke, S., Krikorian, A. and Rausan, J. 1963 Computing the N Best Loopless Paths in a Network,Jounal of SIAM, Vol. 11, No. 4, pp. 1096-1102.
- Sakarovitch, M. 1966 The k Shortest Routes and the k Shortest Chains in a Graph, Operations Research, Center, University of California, Berkeley, Report ORC-32.
- Azevedo, J.A., Costa, M.E.O.S., Madeira, J.J.E.R.S., and Martins, E.Q.V. 1993 An algorithm for the ranking of shortest paths. European Journal of Operational Research, 69:97-106.
- Azevedo, J.A., Madeira, J.J.E.R.S., Martins, E.Q.V., and Pires, F.M.A. 1990 A shortest paths ranking algorithm, Proceedings of the Annual Conference AIRO'90, Models and Methods for Decision Support, Operational Research Society of Italy, 1001-1011.
- Azevedo, J.A., Madeira, J.J.E.R.S., Martins, E.Q.V., and Pires, F.M.A. 994 A computational improvement for a shortest paths ranking algorithm. European Journal of Operational Research, 73:188-191.
- Dreyfus, S.E. 1969 An appraisal of some shortest-path algorithms. Operations Research, 17:395-412.
- Eppstein, D. 1998 Finding the k shortest paths. SIAM Journal on Computing 28:652-673.
- Shier, D. 1974 Computational experience with an algorithm for finding the k shortest paths in a network. Journal of Research of the NBS, 78:139-164.
- Shier, D. 1976 Interactive methods for determining the k shortest paths in a network. Networks, 6:151-159.
- Shier, D. 1979 On algorithms for finding the k shortest paths in a network. Networks, 9:195-214.
- Yen, J.Y. 1971 Finding the k shortest loopless paths in a network. Management Science, 17:712-716.
- Martins, E.Q.V., Pascoal, M.M.B., and Santos. J.L.E. 1997 A new algorithm for ranking loopless paths. Research Report, CISUC.
- Hoffman, W. and Pavely, R., 1959 A Method for the Solution of the Nth Best Problem, Journal of ACM, Vol. 6, No. 4, pp. 506-514.
- Bellman, R. and Kalaba, R 1960 On kth Best Policies, SIAM Journal, Vol. 8, No. 4, pp. 582-588.
- Martins, E.Q.V. 1984 An algorithm for ranking paths that may contain cycles. European Journal of Operational Research, 18:123-130.
- Martins, E.Q.V. and Santos, J.L.E. 1996 A new shortest paths ranking algorithm. E. Martins and J. Santos. A new shortest paths ranking algorithm. Technical report, Departmentof Mathematics, Universityof Coimbra, (http://www.mat.uc.pt/~eqvm).
- Dial, R., Glover, G., Karney, D., and Klingman, D. 1979 A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees. Networks, 9:215-348.
- Martins,E. Q. V., Pascoal, M. M. B., and Santos, J. L. E. 1998 The K shortest paths problem. Research Report, CISUC.
- Bellman, R.E. 1958 On a routing problem. Quarterly Applied Mathematics, 1:425-447.
- Cherkassky, B.V., Goldberg, A.V., and Radzik, T. 1996 Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming, 73:129-196.
- Moore, 1959 E.F. The shortest path through a maze. Proceedings of the International Symposium on the Theory of Switching, Harvard University Press, 285-292.
- Dijkstra, E. 1959 A note on two problems in connection with graphs. Numerical Mathematics, 1:395-412.
- Martins, E. Q. V. and Pascoal, M. M. B. 2003 A new implementation of Yen’s ranking loopless paths algorithm, 4OR, Springer Berlin, 1:121-133.
- El-Amin and Al-Ghamdi. 1993 An expert system for transmission line route selection. Int. Power Engineering Conf, vol. 2, pp. 697-702. Nanyang Technol. Univ, Singapore.
Index Terms
Keywords