Алгоритм Йена

Нахождение K путей минимальной суммарной длины во взвешенном графе с неотрицательными весами. (Алгоритм Йена)

Алгоритм предназначен для нахождения К путей минимальной длины во взвешенном графе соединяющих вершины u1, u2. Ищутся пути, которые не содержат петель. Алгоритм прислал

Итак задача состоит в отыскании нескольких минимальных путей, поэтому возникает вопрос о том чтобы не получить путь содержащий петлю, в случае поиска одного пути минимального веса, это условие выполняется по необходимости, в данном же случае мы используем алгоритм Йена, позволяющий находить K простых кратчайших цепей.

Работа алгоритма начинается с нахождения кратчайшего пути, для этого будем использовать уже описанный алгоритм. Второй путь ищем, перебирая кратчайшие отклонения от первого, третий кратчайшие отклонения от второго и т.д. Более точное пошаговое описание:

1. Найти минимальный путь P1=(v11,...,v1L[1]) .Положить k = 2. Включить P1 в результирующий список.

2. Положить MinW равным бесконечности. Найти отклонение минимального веса, от (kv1)-го кратчайшего пути Pk-1 для всех i=1,2,...,L[k-1], выполняя для каждого i

шаги с 3-го по 6-й.

3. Проверить, совпадает ли подпуть, образованный первыми i вершинами пути Pk-1, с подпутем, образованным первыми i вершинами любого из путей j=1,2,...,kv1. Если да, положить W[vk-1i,vji+1] равным бесконечности в противном случае ничего не изменять (чтобы в дальнейшем исключить получение в результат одних и тех же путей).

4. Используя алгоритм нахождения кратчайшего пути, найти пути от vk-1i к u2, исключая из рассмотрения корни (vk-11,...,vk-1i) (чтобы исключить петли), для этого достаточно положить равными бесконечности элементы столбцов и строк матрицы W, соответствующие вершинам, входящим в корень.

5. Построить путь, объединяя корень и найденное кратчайшее ответвление, если его вес меньше MinW, то запомнить его.

6. Восстановить исходную матрицу весов W и возвратиться к шагу 3.

7. Поместить путь минимального веса (MinW), найденный в результате выполнения шагов с 3 по 6, в результирующий список. Если k = K, то алгоритм заканчивает работу, иначе увеличить k на единицу и вернуться к шагу 2.

Алгоритм использует массив p для результирующего списка путей, и массив length для хранения соответствующих длин, при этом если начиная с некоторого i элементы length[i] равны -1, значит существует только i-1 кратчайших путей без петель.