#algorithm #graph #set #shortest-path
#алгоритм #График #установить #кратчайший путь
Вопрос:
Я не уверен в названии этой проблемы, поэтому на самом деле не смог ее исследовать. У меня есть полный взвешенный график с начальным и конечным узлом и n различными наборами узлов (назовем их красными, синими и зелеными), каждый с m узлами-членами.
Мне нужно найти кратчайший путь от начала до конца и должен пройти ровно через один красный, один синий и один зеленый узел; есть ли алгоритм для этого?
Расширение будет заключаться в том, что мне нужно найти кратчайший путь, сначала посетив синий, затем зеленый, затем красный (опять же, ровно один раз каждый); есть ли для этого?
Комментарии:
1. Я не думаю, что для этого существует конкретный алгоритм. Алгоритмы кратчайшего пути, как правило, исследуют все пути, и с некоторой памятью вы можете отслеживать, какие пути соответствуют вашим критериям обязательного прохождения. Среди тех, которые соответствуют вашим критериям, вы бы отсортировали и выбрали кратчайший.
Ответ №1:
Часть расширения кажется проще.
Предполагая, что каждый узел имеет цвет (это правда?) все, что вам нужно сделать, это удалить ребра, которые нарушают желаемую последовательность цветов.
Например, удалите все ребра, выходящие из начала, кроме тех, которые ведут к синему узлу. Аналогично, удалите все ребра, оставляющие синий узел, кроме тех, которые ведут к зеленому узлу.
Затем вы можете просто запустить стандартный алгоритм кратчайшего пути (например, Дейкстры) на сокращенном графике.
Если количество цветов не слишком велико, вы можете адаптировать тот же алгоритм для решения исходной задачи. Идея состоит в том, чтобы найти кратчайший путь (используя алгоритм, описанный выше) для каждой перестановки цветов.