Существует ли оптимальный алгоритм для поиска самого длинного кратчайшего пути в сети?

13

У меня есть большой набор линейных сетей, и я хотел бы найти два конца каждой сети, которые являются наиболее удаленными друг от друга вдоль сети (на изображении ниже это будет от D до K). Грубое решение этой проблемы состоит в том, чтобы вычислить кратчайший путь по сети для каждой пары источников, но у меня есть сотни сетей с тысячами концов, поэтому вычисление каждого возможного пути довольно трудоемко.

Есть ли оптимальный способ вычислить это без грубой силы? Могу ли я исключить некоторые пункты на основе некоторых умных правил?

Как эффективно найти красный путь?

РЕДАКТИРОВАТЬ: я добавил иллюстрацию самого длинного пути, упомянутого @Alex Tereshenkov, чтобы прояснить мой вопрос. Черный путь является результатом алгоритма самого длинного пути (самый длинный путь без повторения каких-либо вершин). В моем случае представьте, что вы входите в сеть с одной из букв, и вам нужно как можно быстрее перейти к другой букве. К каким двум буквам сложнее всего присоединиться? введите описание изображения здесь

radouxju
источник
безумная краска скиллз!
Адам

Ответы:

6

Я думаю, что вы, возможно, ищете график диаметра вашей сети. Есть пара вопросов по stackexchange, которые затрагивают эту тему, например:

Большинство алгоритмов предлагают сначала вычислить «кратчайшие пути из всех пар» и выбрать самый длинный из них, но я нашел сообщение в блоге Кушика Нараянана, в котором предлагается альтернативный подход, который может быть более оптимальным (я не проверял), который перебирает каждую вершину и находит ее самую дальнюю пару:

Мы можем вычислить путь из вершины V1 так, чтобы он был кратчайшим путем между V1 и одной из вершин и был длиннее кратчайшего пути между любыми другими вершинами. Смотрите этот пост для алгоритма. Затем мы можем перебрать каждую вершину и найти самый длинный путь с каждой вершиной в качестве корня. Как только у нас будет список всех самых длинных кратчайших путей, мы можем найти тот, который имеет максимальное значение, и вернуть его.

mkadunc
источник
спасибо, диаметр графика был именно тем, что я ищу, и эвристика псевдодиаметра работает в моем случае. Я только что выучил новые слова там!
Радучжу,
7

Согласно странице википедии проблема длинного пути , эта проблема

... является NP-сложным, что означает, что оно не может быть решено за полиномиальное время для произвольных графов, если P = NP. Также известны более сильные результаты твердости, показывающие, что их трудно приблизить. Тем не менее, он имеет линейное временное решение для направленных ациклических графов, что имеет важные приложения для поиска критического пути в задачах планирования.

Если вы работаете с (или можете представить свой график как DAG ), тогда networkxпакет Python позволит вам его вычислить. Ищите функцию dag_longest_path.

Если я что-то не упустил, вам нужно будет рассчитать длину между узлами графа и отсортировать их, что, к сожалению, будет работать только за линейное время , то есть для этого нет эффективного алгоритма.

Алекс Терешенков
источник
Спасибо за ответ, уже +1 из-за информации. Тем не менее, я ищу самый длинный из кратчайших путей в сети (в моем примере нет обходного пути к B или H). Поэтому ваше решение не совсем то, что я ищу, даже если оно намекает на то, что «грубая сила», вероятно, является единственным решением.
Радучжу
@radouxju, ну я вижу. Ну, давайте посмотрим , если ген заметит это, он имеет большой опыт работы с графами, может быть , он имеет некоторые яркие идеи.
Алексей Терешенков