Algorytm dewiacyjny dla problemu wyznaczania K najkrótszych ścieżek

• Autorzy: Widuch J. , Szołtysek M.

Warianty tytułu

EN

Deviation algorithm for solving the K shortest path problem

• Języki publikacji: PL

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

skierowany graf ważony; ścieżka; podścieżka; waga ścieżki; najkrótsza ścieżka; drzewo ścieżek; algorytm Dijkstry

EN

directed weighted graph; path; subpath; weight of path; shortest path; tree of paths; Dijkstra algorithm

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Studia Informatica
• Rocznik: 2011
• Tom: Vol. 32, nr 1A
• Strony: 55--77
• Opis fizyczny: Bibliogr. 23 poz.

Twórcy

autor

Widuch J.

autor

Szołtysek M.

• Politechnika Śląska, Instytut Informatyki, ul. Akademicka 216, 44-100 Gliwice, Polska,

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.