Нахождение кратчайшего пути между двумя узлами с набором запрещенных узлов

Question

У меня есть неориентированный и невзвешенный график, на котором я хотел бы найти кратчайший путь между двумя введенными узлами.Существует также набор запрещенных узлов.Как найти кратчайший путь, если мне разрешено посетить максимум один узел из набора запрещенных узлов?

Answer 1

1. Выполните BFS, начиная с END - всякий раз, когда он достигает запрещенного узла, обновляйте его distance_from_end и не добавляйте его соседей в вашу очередь.Все запрещенные узлы, которые не посещены, не должны иметь действительного distance_from_end.

2. Сделайте то же самое, что (1), но начиная с START и обновляя distance_from_start

3. Для всех запрещенных узлов возьмите тот, который имеет минимальное расстояние: от расстояния + расстояние до конца.(обратите внимание, что этот узел может не существовать, так как узлы могут иметь недопустимые значения в этих полях и, следовательно, их следует игнорировать)

4. Сделать BFS от начала до конца, отменить все запрещенные узлы, кромеодин найден в (3).

5. Из BFS, выполненной в 4, вы либо:

   • найдете путь, который не пересекает ни один запрещенный узел, которыйкороче, чем тот, который пересекает его.
   • находит путь, пересекающий запрещенный узел, в этом случае его длина должна быть равна (distance_from_start + distance_from_end) для этого узла.
   • вообще не найти пути, это означает, что вы не нашли узел на шаге (3) и что после удаления всех запрещенных узлов из графа вы получите график, где START и END находятся в разных разделах.

Answer 2

• Создание BFS с начала, не проходите через запрещенные узлы.
• Создание BFS с конца, не проходите через запрещенные узлы.
• Инициализируйте расстояние пути какdist (начало, конец).Это будет бесконечно, если ваши первые bfs не достигли конца.
• Для каждого запрещенного узла сделайте расстояние пути = min (расстояние пути, dist (начало, запрещенный узел) + dist (конец, запрещенный узел))
• Расстояние пути возврата

Сложность: такая же, как у BFS

Answer 3

Выполнить BFS, но с графиком в качестве параметра, а не в качестве глобальной справочной таблицы.В любой ветке, когда вы посещаете запрещенный узел, вы останавливаете и удаляете все другие запрещенные узлы из графа, который вы переходите на следующий уровень.

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

Answer 4

Вы можете создать первую BFS, которая перечисляет доступные запрещенные узлы с самого начала (но не может пересекать ее).Затем вы записываете расстояние от начала.В вашем примере 2 для каждого запрещенного узла.

Вы делаете то же самое с конечным узлом, задавая пути 2 и 1. На вашем пути.

Затем вы запрещаете лучший запрещенный узел (минимальное расстояние от начала +расстояние от конца).И, наконец, вы делаете BFS в полном графе.

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