У меня есть большой набор линейных сетей, и я хотел бы найти два конца каждой сети, которые являются наиболее удаленными друг от друга вдоль сети (на изображении ниже это будет от D до K). Грубое решение этой проблемы состоит в том, чтобы вычислить кратчайший путь по сети для каждой пары источников, но у меня есть сотни сетей с тысячами концов, поэтому вычисление каждого возможного пути довольно трудоемко.
Есть ли оптимальный способ вычислить это без грубой силы? Могу ли я исключить некоторые пункты на основе некоторых умных правил?
РЕДАКТИРОВАТЬ: я добавил иллюстрацию самого длинного пути, упомянутого @Alex Tereshenkov, чтобы прояснить мой вопрос. Черный путь является результатом алгоритма самого длинного пути (самый длинный путь без повторения каких-либо вершин). В моем случае представьте, что вы входите в сеть с одной из букв, и вам нужно как можно быстрее перейти к другой букве. К каким двум буквам сложнее всего присоединиться?
Ответы:
Я думаю, что вы, возможно, ищете график диаметра вашей сети. Есть пара вопросов по stackexchange, которые затрагивают эту тему, например:
Большинство алгоритмов предлагают сначала вычислить «кратчайшие пути из всех пар» и выбрать самый длинный из них, но я нашел сообщение в блоге Кушика Нараянана, в котором предлагается альтернативный подход, который может быть более оптимальным (я не проверял), который перебирает каждую вершину и находит ее самую дальнюю пару:
источник
Согласно странице википедии проблема длинного пути , эта проблема
Если вы работаете с (или можете представить свой график как DAG ), тогда
networkx
пакет Python позволит вам его вычислить. Ищите функциюdag_longest_path
.Если я что-то не упустил, вам нужно будет рассчитать длину между узлами графа и отсортировать их, что, к сожалению, будет работать только за линейное время , то есть для этого нет эффективного алгоритма.
источник