Есть следущая задача:найти минимальный путь и найти второй минимальный путь,при этом второй минимальный путь не должен полностью содержать первый минимальный путь.
Примеры( "1)"- минимальный путь, "2)"- второй минимальный путь , указаны номера узлов): 1.1) 1-3-5 2) 1-2-3-4-5 Неправильно т.к. 2 путь полность содержит первый.
2.1) 1-3-5 2) 1-2-5 Правильно т.к. 2 путь не содержит 3 узел с 1 пути.
3.1) 1-3-5 2) 2-4-5 Тоже может быть правильно правильно.
Реализация алгоритма следущая:
- Используя алгоритм Дейкстры найти первый минимальный путь.
- Записать полученный минимальный путь (т.е. номера узлов) в массив.
- ?????? И собственно тут возникает проблема - как начать находить следущие минимальные пути. Предположение , что вторым минимальным значением является второе минимальное значение расстояния соседей целевого узла(Пример:есть целевой узел N с соседами N-1(расстояние - 6) N-2(8) N-3(11) т.е. теоретически вторым минимальным является путь через N-2) не всегда верно т.к. возможно нужно в первом пути поменять узел в середине и получится меньшее значение(в примере нужно будет на пути к N-1 поменять используемое ребро N-8->N-5 с весом 1 на ребро N-9->N-5 с весом 2 ,расстояния до N-8 и N-9 идентичные, и тогда получится минимальным путь с весом 7).
Вопрос - как найти этот второй путь?