We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 November 2024
Call for Paper
December Edition
IJCA solicits high quality original research papers for the upcoming December edition of the journal. The last date of research paper submission is 20 November 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Comprehensive Study on Computational Methods for K-Shortest Paths Problem

by Kalyan Mohanta
journal cover thumbnail

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

@article{ 10.5120/5048-7444,
author = { Kalyan Mohanta },
title = { Comprehensive Study on Computational Methods for K-Shortest Paths Problem },
journal = { International Journal of Computer Applications },
issue_date = { February 2012 },
volume = { 40 },
number = { 14 },
month = { February },
year = { 2012 },
issn = { 0975-8887 },
pages = { 22-26 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume40/number14/5048-7444/ },
doi = { 10.5120/5048-7444 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:28:04.291283+05:30
%A Kalyan Mohanta
%T Comprehensive Study on Computational Methods for K-Shortest Paths Problem
%J International Journal of Computer Applications
%@ 0975-8887
%V 40
%N 14
%P 22-26
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
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
  1. 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.
  2. Pollack, M. 1961 The k-th Best Route Through a Network, Operations Research, Vol. 9, No. 4, pp. 578-580.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. Dreyfus, S.E. 1969 An appraisal of some shortest-path algorithms. Operations Research, 17:395-412.
  9. Eppstein, D. 1998 Finding the k shortest paths. SIAM Journal on Computing 28:652-673.
  10. 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.
  11. Shier, D. 1976 Interactive methods for determining the k shortest paths in a network. Networks, 6:151-159.
  12. Shier, D. 1979 On algorithms for finding the k shortest paths in a network. Networks, 9:195-214.
  13. Yen, J.Y. 1971 Finding the k shortest loopless paths in a network. Management Science, 17:712-716.
  14. Martins, E.Q.V., Pascoal, M.M.B., and Santos. J.L.E. 1997 A new algorithm for ranking loopless paths. Research Report, CISUC.
  15. 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.
  16. Bellman, R. and Kalaba, R 1960 On kth Best Policies, SIAM Journal, Vol. 8, No. 4, pp. 582-588.
  17. Martins, E.Q.V. 1984 An algorithm for ranking paths that may contain cycles. European Journal of Operational Research, 18:123-130.
  18. 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).
  19. 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.
  20. Martins,E. Q. V., Pascoal, M. M. B., and Santos, J. L. E. 1998 The K shortest paths problem. Research Report, CISUC.
  21. Bellman, R.E. 1958 On a routing problem. Quarterly Applied Mathematics, 1:425-447.
  22. Cherkassky, B.V., Goldberg, A.V., and Radzik, T. 1996 Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming, 73:129-196.
  23. 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.
  24. Dijkstra, E. 1959 A note on two problems in connection with graphs. Numerical Mathematics, 1:395-412.
  25. 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.
  26. 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

Computer Science
Information Sciences

Keywords

Shortest path K-shortest paths Optimality principle Algorithm Computational complexity

Powered by PhDFocusTM