Задача о поиске простого пути заданной длины между заданными вершинами в неориентированном графе

В настоящее время теория графов является одним из ключевых инструментов для решения прикладных задач: моделирования транспортных систем, задач социологии, составления расписаний и многих других. Для их решения необходимы эффективные алгоритмы. К таким задачам относится и задача о поиске простого пути заданной длины между заданными вершинами в неориентированном графе. Целью данной работы является определение самого эффективного алгоритма для решения рассматриваемой задачи.
В работе рассматриваются два алгоритма для решения поставленной задачи: модификация существующего алгоритма Йена, изначально предназначенного для поиска k простых путей между заданными вершинами в графе, и новый разработанный автором алгоритм. Приведена оценка временной сложности для обоих алгоритмов в худшем случае. Выполнена реализация обоих алгоритмов на языке Python для численных экспериментов. Проведены численные эксперименты для сравнения времени работы алгоритмов на графах с различной степенью разреженности. Численно выявлен случай, в котором разработанный алгоритм работает значительно быстрее модификации алгоритма Йена.