Вычисление кратчайшего пути от заданного узла ко всем остальным узлам, некоторые узлы запрещены для пути
Я хотел бы реализовать следующее в Python, но не уверен, с чего начать. Есть ли хорошие модули для задач кратчайшего пути такого типа?
Я пытаюсь определить кратчайший путь от конкретного атома (узла) ко всем другим атомам (узлам) в данной коллекции координат XYZ для трехмерной химической структуры (график). Связи между атомами (узлами) являются ребрами, для которых разрешено перемещение от узла к узлу.
Я пытаюсь отфильтровать определенные атомы (узлы) от молекулы (графа) на основе возможности соединения от выбранного центрального узла.
** Для рассмотренных путей я ЗАПРЕЩАЕТСЯ пересекать определенные атомы (узлы). Если кратчайший путь от A до B проходит через запрещенный узел, этот ответ запрещен. Кратчайший путь от А до В не должен включать запрещенный узел **
Если кратчайший путь от выбранного центрального атома (A) к другому другому узлу (B) ВКЛЮЧАЕТ запрещенный узел, и нет другого доступного пути от A до B через доступные ребра (связи), то узел B следует удалить из окончательный набор координат XYZ (узлов) для сохранения.
Это следует повторить для A-C, A-D, A-E и т. Д. Для всех других атомов (узлов) в структуре (графике).
Заранее спасибо за любую помощь, которую вы можете предложить.
2 ответа
Убедитесь, что все ребра, которые привели бы к запрещенному узлу (ам), имеют бесконечную стоимость, и какой бы алгоритм обхода графов вы ни использовали, он будет работать с ним автоматически.
В качестве альтернативы просто удалите запрещенные узлы из рассмотрения алгоритмом обхода графа.
Чтобы ответить на первую часть вашего вопроса, я рекомендую networkx. Это графическая библиотека общего назначения, в которую довольно легко попасть (я использовал ее в своей докторской диссертации).