ОПТИМИЗАЦИИ АЛГОРИТМА ПОИСКА K КРАТЧАЙШИХ ПУТЕЙ

Авторы: 
А. Р. Герб, Е. Е. Девятых, Г. А. Омарова
УДК: 
519.17—51-7
DOI: 
10.24412/2073-0667-2026-1-40-49
Аннотация: 

EDX: RGXRWO
В работе исследуются алгоритмы поиска к кратчайших путей. Реализован оптимизированный алгоритм для нахождения к кратчайших простых (без петель) путей в ориентированном графе. Алгоритм основан на идеях классической версии алгоритма Иена и алгоритма построения обратного дерева, обе реализации имеют сложность О(kn(m + n log n)).

Исследования выполнены в рамках государственного задания ИВМиМГ СО РАН FWNM-2025-0001.

Список литературы

  1. Egli W., Kraus М. Shortest paths in chemical kinetic applications // Phys. Chem. Chem. Phys. 2003. Vol. 5. P. 3916-3920.
  2. Yen Jin Y., Finding the К shortest loopless paths in a network // Manag. Sci. 1971. Vol. 17. P. 712-716.
  3. Hoffman R., Pavley R. A method for the solution of the nth best path problem // J. of the Association for Computing Machinery. 1959. Vol. 6, N 4. P. 506-515.
  4. Bellman R., Kalaba R. On kth best policies // J. of SIAM. 1960. Vol. 8, N 4. P. 582-588.
  5. Bock F., Kanther H., Haynes J. An algorithm (the rh best path algorithm) for findinq and ranking paths through a network // Research Report, Armour Research Foundation. Chicago, Illinois, 1957.
  6. Clarke S., Krikorian A., Rausan J. Computing the N best loopless paths in a network // J. of SIAM. 1963. Vol. 11, N 4. P. 1096-1102.
  7. Dijkstra E. W. A note on two problems in connexion with graphs // Numerische Mathematik. 1959. Vol. 1. P. 269-271.
  8. Pollack M. The kth best route through a network // Operations Research. 1961. Vol. 9, N 4. P. 578.
  9. Sakarovitch M. The k shortest routes and the k shortest chains in a graph // Operations Research Center Report N 66-32. University of California, Berkeley. 1966.
  10. Coudert D., Al Zoobi A., Nisse N. Space and time trade-off for the k shortest simple paths problem space and time trade-off for the k shortest simple paths problem // 18th International Symposium on Experimental Algorithms (SEA 2020). Art. N 18. P. 18:1-18:13.
  11. Kurz D., Mutzel P. A sidetrack-based algorithm for finding the k shortest simple paths in a directed graph //In Int. Symp. on Algorithms and Computation (ISAAC), Schloss Dagstuhl, 2016. Vol. 64 of LIPIcs. P. 49:1-49:13.
  12. Frigioni D., Marchetti-Spaccamela A., Nanni U. Fully dynamic algorithms for maintaining shortest paths trees // J. of Algorithms. 2000. Vol. 34, N 2. P. 251-281.
  13. [Электрон, pec.]: https://www.diag.uniromal.it/challenge9/download.html.
  14. [Электрон, pec.]: https://snap.stanford.edu/data/ca-AstroPh.html.
  15. [Электрон, pec.]: https://snap.stanford.edu/data/ca-CondMat.html.
  16. [Электрон, pec.]: https://snap.stanford.edu/data/ca-GrQc.html.
  17. [Электрон, pec.]: https://snap.stanford.edu/data/ca-HepTh.html.

 

Ключевые слова: 
граф, путь, простой путь, дерево, обход графа.
Номер журнала: 
1(70) 2026 г.
Год: 
2026
Адрес: 
Институт вычислительной математики и математической геофизики СО РАН, 630090, Новосибирск, Россия Новосибирский государственный университет, 630090, Новосибирск, Россия
Библиографическая ссылка: 
Герб А. Р., Девятых Е. Е., Омарова Г. А. Оптимизации алгоритма поиска k- кратчайших путей //"Проблемы информатики", 2026, № 1, с.40-49.  DOI: 10.24412/2073-0667-2026-1-40-49.