1
В настоящее время я пытаюсь выяснить, эффективный способ, чтобы найти все узлы на некоторых путей между двумя узлами (например, X и Y) в ориентированном граф.эффективно найти все узлы на некотором пути между двумя узлами в ориентированном графе
Моя первая мысль заключалась в том, чтобы запустить BFS из X, запустить BFS из Y и перейти на пересечение посещенных узлов. Обратите внимание, что мне не нужно перечислять все пути между X и Y, просто найдите все узлы, которые лежат на пути от X до Y.
Мой вопрос в том, есть ли более оптимизированный способ сделать это?
Я не уверен, как создать вывод всех узлов по всем путям от X до Y в состояние цели; Я использовал только A * в контексте нахождения кратчайшего/оптимального пути к состоянию цели (т. Е. Путь с наименьшей стоимостью/наименьшей стоимостью от X до Y). – kk415kk
Если бы я понял, что узлы между X и Y будут такими же, как узлы, которые пройдут по этому пути. Тогда эта проблема будет одинаковой при поиске любого пути между X и Y, найдет кратчайший путь от X до Y ok? Может, я не понял ваш вопрос. – Joelmob
Yup, найти кратчайший путь может быть частью проблемы, но мне нужно найти все узлы на всех путях от X до Y. Может быть несколько путей разной длины от X до Y. A * будет разумно вести поиск чтобы избежать поиска некоторых частей других путей. – kk415kk