Warianty tytułu
Deviation algorithm for solving the K shortest path problem
Języki publikacji
Abstrakty
Jednym z badanych problemów teorii grafów jest problem wyznaczenia najkrótszej ścieżki. Rozszerzeniem tego problemu jest problem wyznaczenia K (K > 1) najkrótszych ścieżek. Badane są dwa warianty tego problemu. W pierwszym dopuszcza się wyznaczenie ścieżek zawierających cykle, a w drugim są wyznaczane wyłącznie ścieżki acykliczne. W pracy został przedstawiony algorytm dewiacyjny, umożliwiający wyznaczenie K najkrótszych ścieżek, które mogą zawierać cykle.
One of the studied problems of the graph theory is the shortest path problem. An extension of this problem is the problem of finding K (K > 1) shortest paths. Two variants of this problem are studied. In the first case path containing cycles are allowed, and in the second are determined only loopless paths. In the paper a deviation algorithm for solving K shortest paths, which may contain cycles is shown.
Czasopismo
Rocznik
Tom
Strony
55-77
Opis fizyczny
Bibliogr. 23 poz.
Twórcy
autor
autor
- Politechnika Śląska, Instytut Informatyki, ul. Akademicka 216, 44-100 Gliwice, Polska, jacek.widuch@polsl.pl
Bibliografia
- 1. Azevedo J. A., Costa M. E O. S., Madeira J. J. R E. S., Martins E. Q. V.: An algorithm for the ranking of shortest paths. European Journal of Operational Research. Vol. 69, 1993, s. 97-106.
- 2. Azevedo J. A., Madeira J. J. R. E. S., Martins E. Q. V., Pires F. M. A.: A computational improvement for a shortest paths ranking algorithm. European Journal of Operational Research, Vol. 73, 1994, s. 188-191.
- 3. Bellman R.: On a routing problem Quarterly of Applied Mathematics. Vol. 16, No. 1, 1958, s. 87-90.
- 4. Cormen T., Leiserson C., Rivest R., Stein C.: Wprowadzenie do algorytmów. WNT, Warszawa 2004.
- 5. Dijkstra E. W.: A note on two problems in connexion with graphs. Numerical Mathematics, Vol. 1, 1959, s. 269-271.
- 6. Dreyfus S. E.: .An appraisal of some shortest-path algorithms. Operations Research. Vol. 17, 1969, s. 395-412.
- 7. Eppstein D.: Finding the k shortest paths. SIAM Journal on Computing. Vol. 28, No. 2, 1998, s. 652-673.
- 8. Floyd R. W.: .Algorithm 97: Shortest path. Communications of the ACM, Vol. 5, No. 6, 1962, s. 345.
- 9. Ford Jr L. R., Fulkerson D. R.: Flows in networks. Princeton University Press. 1962.
- 10. Hershberger J., Maxel M., Suri S.: Finding the k Shortest Simple Paths: A New Algorithm and Its Implementation. In Proceedings of ALENEX'03, 2003, s. 26-36.
- 11. Johnson D. B.: Efficient algorithms for shortest paths in sparse networks. Journal of the ACM, Vol. 24, No., 19771, s. 1-13.
- 12. Jungnickel D.: Graphs, networks and algorithms. Springer, Berlin 1999.
- 13. Katoh N., Ibaraki T., Mine H.: An efficient algorithm for k shortest simple paths. Networks, Vol. 12.1982, s. 411-427.
- 14. Lipski W.: Kombinatoryka dla programistów. WNT, Warszawa 1989.
- 15. Martins E. Q. V., Pascoal M. M. B., Santos J. L. E., .An algorithm for ranking paths that may contain cycles. European Journal of Operational Research. Vol. 18, 1984, s. 123-130.
- 16. Martins E. Q. V., Pascoal M. M. B., Santos J. L. E.: Deviation algorithms for ranking shortest paths. International Journal of Foundations of Computer Science. Vol. 10, No. 3, 1999. s. 247-261.
- 17. Martins E. Q. V., Santos J. L. E.: A new shortest paths ranking algorithm. Investigação Operacional, Vol. 20, No. 1, 2000, s. 47-62.
- 18. Perko A.: Implementation of algorithms for k shortest loopless paths. Networks, Vol. 16, 1986, s. 149-160.
- 19. Reingold E. M., Nievergelt J., Deo N.: Algorytmy kombinatoryczne. PWN, Warszawa 1985.
- 20. Shier D R.: On algorithms for finding the k shortest paths in a network. Networks, Vol. 9, 1979, s. 195-214.
- 21. Syslo M., Deo N., Kowalik J.: Algorytmy optymalizacji dyskretnej z programami w języku Pascal. PWN, Warszawa 1999.
- 22. Yen J. Y.: Finding the k shortest loopless paths in a network. Management Science, Vol. 17, 1971, s. 712-716.
- 23. Warshall S.: A theorem on boolean matrices. Journal of the ACM. Vol. 9, No. 1. 1962, s. 11-12.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.baztech-article-BSL2-0025-0059