A Class of Label-Correcting Methods for the K Shortest Paths Problem

References

• Azevedo J. A., Costa M. E. O., Silvestre Madeira J. J. E. R., Martins E. Q. V. An algorithm for the ranking of shortest paths. Eur. J. of Oper. Res. (1993) 69:97–106Crossref, Google Scholar
• Azevedo J. A., Silvestre Madeira J. J. E. R., Martins E. Q. V., Pires F. M. A. A shortest paths ranking algorithm. Proceedings of the AIRO 90 Conference (1990) 1001–1012Google Scholar
• Azevedo J. A. A computational improvement for a shortest paths ranking algorithm. Eur. J. Oper. Res. (1994) 73:188–191Crossref, Google Scholar
• Bako A., Kas P. Determining the k-th shortest path by matrix method. Szigma (1977) 10:61–66Google Scholar
• Beilner H. An algorithm for finding all k-shortest distances in a network. Computing (1972) 10:205–220Crossref, Google Scholar
• Bellman R.Dynamic Programming (1957) (Princeton University Press, Princeton, N.J) Google Scholar
• Bertsekas D. P. A simple and fast label correcting algorithm for shortest paths. (1992) . Technical Report, LIDS-P-2098, Laboratory for Information and Decision Systems, MIT, Cambridge, MAGoogle Scholar
• Bertsekas D. P. A simple and fast label correcting algorithm for shortest paths. Networks (1993) 23:703–709Crossref, Google Scholar
• Bertsekas D. P.Linear Network Optimization: Algorithms and Codes (1991) (M.I.T. Press, Cambridge, MA) Google Scholar
• Bertsekas D. P., Guerriero F., Musmanno R. Parallel asynchronous label-correcting methods for shortest paths. J. of Optim. Theory and Appl. (1996) 88:297–321Crossref, Google Scholar
• Bock F., Kantner H., Rausan J. An algorithm (the r-th best path algorithm) for finding and ranking paths through a network. (1957) . Research Report. Armour Research Foundation, Chicago, IllinoisGoogle Scholar
• Brown A. A., Bartholomew-Biggs M. C. Some effective methods for unconstrained optimization based on the solution of systems of ordinary differential equations. (1987) . Technical Report 178. Numerical Optimization Centre, Hatfield Polytechnic, Hatfield, UKGoogle Scholar
• Carraresi P., Sodini C. A binary enumeration tree to find K shortest paths. Proceedings of the 7th Symposium on Operations Research (1983) Switzerland:177–188Google Scholar
• Cherkassky B. V., Goldberg A. V. Negative-cycle detection algorithms. Proceedings of the 4th European Symposium on Algorithms (1996) Barcelona, SpainCrossref, Google Scholar
• Cherkassky B. V., Goldberg A. V., Radzik T. Shortest Paths Algorithms: Theory and Experimental Evaluation. Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (1993) Arlington, Virginia:516–525Google Scholar
• Chong E. I., Maddila S. R., Morley S. T. On finding single-source single-destination K shortest paths. Proceedings of the 7th Int. Conf. Computing and Information (1995) Ontario, CanadaGoogle Scholar
• Clarke S., Krikorian A., Rausan J. Computing the N best loopless path in a network. J. of SIAM (1963) 11:1096–1102Google Scholar
• Dijkstra E. W. A Note on Two Problems in Connection with Graphs. Num. Math. (1959) 1:269–271Crossref, Google Scholar
• Dreyfus S. E. An appraisal of some shortest-path algorithms. Oper. Res. (1969) 17:395–412Link, Google Scholar
• Eppstein D. Finding the K shortest paths. SIAM J. Comp. (1999) 28:653–674Google Scholar
• Gallo G., Pallottino S. Shortest path methods: a unified approach. Math. Programming Stud. (1986) 26:38–64Crossref, Google Scholar
• Glover F., Glover R., Klingman D. The threshold shortest path algorithm. Networks (1986) 14:256–282Google Scholar
• Guerriero F., Musmanno R. Label-setting methods for the K shortest paths problem. (1996) . Technical Report. ParCoLab 9/96, Department of Electronics, Informatics and Systems, University of CalabriaGoogle Scholar
• Katoh N., Ibaraki T., Mine H. An efficient algorithm for K shortest simple paths. Networks (1982) 4:411–427Crossref, Google Scholar
• Klingman D., Napier A., Stutz J. NETGEN: a program for generating large-scale (un)capacitated assignment, transportation, and minimum cost flow network problems. Management Sci. (1974) 20:814–822Link, Google Scholar
• Lalov P. I., Vasilćeva T. G. Transformation on an oriented graph for finding the K shortest paths. Math. Rev. (1992) 92mGoogle Scholar
• Lawler E. L. A procedure for computing the K best solutions to discrete optimization problems and its application to shortest paths problems. Management Sci. (1972) 18:401–405Link, Google Scholar
• Leo J., Oda T. A realtime algorithm for finding the k shortest paths minimizing travel time and right turns. Proceedings of the 13th Road Traffic Engineering Research Conf. (1993) Tokyo:133–136Google Scholar
• Minieka E. On computing sets of shortest paths in a graph. Comm. ACM (1974) 17:351–353Crossref, Google Scholar
• Perko A. Implementation of algorithms for K shortest loop-less paths. Networks (1986) 16:149–160Crossref, Google Scholar
• Pollack M. The Kth best route through a network. Oper. Res. (1961a) 9:578–580Link, Google Scholar
• Pollack M. Solutions of the Kth route through a network. J. Math. Anal. Appl. (1961b) 3:547–559Crossref, Google Scholar
• Sakarovitch M. The k shortest routes and the k shortest chains in a graph. (1966) . Technical Report, ORC 66-32, Operations Research Center, University of California, Berkeley, USAGoogle Scholar
• Shier D. R. Computational experience with an algorithm for finding the K shortest paths in a network. J. of Res. of the Nat. Bureau of Standards Sect. B. Math. Sci. (1974) 78B:139–165Crossref, Google Scholar
• Shier D. R. On algorithms for finding the K shortest paths in a network. Networks (1979) 9:195–214Crossref, Google Scholar
• Topkis D. M. A K shortest path algorithm for adaptive routing in communications networks. IEEE Trans. Comm. (1988) 36:855–859Crossref, Google Scholar
• Yen J. Y. Finding the K shortest loopless paths in a network. Management Sci. (1971) 17:712–716Link, Google Scholar