Задача о кратчайших путях с ограничением на максимальное количество ребер, входящих в путь

Abstract

In this article two problems arc analyzed: the problem of finding all shortest paths for all pairs of vertices with the constraint on the ceiling amount of edges, included in the path, and the problem of forming lists of all constraint paths for all pairs of vertices ordered by the weight. The exact algorithms of solving these problems are formulated. Рассматривается задача нахождения всех кратчайших путей и задача построения упорядоченных по весу списков всех путей для всех пар вершин с дополнительным ограничением на длину пути. Исследуются преобразования матриц весов путей и связь этих преобразований с длинами соответствующих путей, а также строятся алгоритмы решения поставленных задач.