Алгоритм стягивания путей для задачи поиска простого пути заданной длины
Получена: 09.11.2026 Доработана: 10.11.2026 Принята: 10.11.2026
Опубликована: 2026 год, том 30, выпуск 4, С. 156–159
Аннотация
В работе рассматривается задача поиска простого пути заданной длины между заданными вершинами в связном неориентированном взвешенном графе без кратных ребер и петель, все веса ребер которого являются положительными числами. Данная задача возникает при планировании транспортных маршрутов с гарантированной задержкой или при анализе графов, возникающих в микробиологии. Авторами предложен новый алгоритм для решения задачи поиска простого пути заданной длины в графе. Разработанный алгоритм основан на постепенном преобразовании графа и отсечении простых путей, которые не могут являться частью искомого простого пути. В работе представлены оценки временной и пространственной сложности нового алгоритма в среднем и худшем случаях, а также представлены результаты численных экспериментов по сравнению данного алгоритма с модифицированным алгоритмом Йена.
Ключевые слова: алгоритм Йена, поиск простых путей, случайный граф Эрдеша-Реньи.
BibTeX
@article{IS-Vaschenko-Mastikhina2026,
author = {Ващенко, Максим Игоревич and Мастихина, Анна Антоновна},
title = {{Алгоритм стягивания путей для задачи поиска простого пути заданной длины}},
journal = {Интеллектуальные системы. Теория и приложения},
year = {2026},
volume = {30},
number = {4},
pages = {156--159},
}
AMSBIB
\RBibitem{IS-Vaschenko-Mastikhina2026}
\by М.\,И.~Ващенко, А.\,А.~Мастихина
\paper Алгоритм стягивания путей для задачи поиска простого пути заданной длины
\jour Интеллектуальные системы. Теория и приложения
\yr 2026
\vol 30
\issue 4
\pages 156--159
EN