Вычисление расходящихся путей на дополнительных кольцах

Question

Мне нужно вычислить два пути от A до B на следующем графике с ограничением на то, что пути не могут иметь общие ребра:

хм, ладно, не могу публиковать изображения, вот ссылка .

Все ребра имеют положительные веса; для этого примера я думаю, что мы можем предположить, что они равны. Мой наивный подход заключается в использовании алгоритма Джикстры для вычисления первого пути, показанного на втором графике на изображении выше.

Затем я удаляю ребра из графика и пытаюсь вычислить второй путь, который не удался. Существует ли вариант Джикстра, Беллмана-Форда (или чего-то еще), который будет рассчитывать пути, показанные на третьей диаграмме выше? (Без специальных знаний и удаления подтекстовой ссылки, это то, что я имею в виду)

Answer 1

То, что вы ищете, это непересекающиеся края. Теорема Менгера даст вам максимальное количество непересекающихся путей. Чтобы найти самую короткую пару, взгляните на алгоритм Edge disjoint для самой короткой пары :

1. Запустить алгоритм самой короткой пары для данной пары вершин
2. Заменить каждое ребро кратчайшего пути (эквивалентно двум противоположно направленным дугам) одной дугой, направленной к исходной вершине
3. Сделать длину каждой из вышеперечисленных дуг отрицательной
4. Запуск алгоритма кратчайшего пути (Примечание: алгоритм должен принимать отрицательные затраты)
5. Сотрите перекрывающиеся ребра двух найденных путей и поменяйте местами направление оставшихся дуг на первом кратчайшем пути так, чтобы каждая дуга на нем была теперь направлена ​​к вершине стока. Нужная пара путей приводит к результатам.