Хороший алгоритм для нахождения диаметра (редкого) графика?

Well, I've put a little bit of thought on the problem, and a bit of googling, and I'm sorry, but I can't find any algorithm that doesn't seem to be "just find all pairs shortest path".

However, if you assume that Floyd-Warshall is the only algorithm for computing such a thing (Big-Theta of |V|^3), then I have a bit of good news for you: Johnson's Algorithm for Sparse Graphs (thank you, trusty CLRS!) computes all pairs shortest paths in (Big-Oh (|V|^2 * lgV + VE)), which should be asymptotically faster for sparse graphs.

Wikipedia says it works for directed (not sure about undirected, but at least I can't think of a reason why not), here's the link.

Is there anything else about the graph that may be useful? If it can be mapped easily onto a 2D plane (so, its planar and the edge weights obey the triangle inequality [it may need to satisfy a stricter requirement, I'm not sure]) you may be able to break out some geometric algorithms (convex-hull can run in nlogn, and finding the farthest pair of points is easy from there).

Hope this helps! - Agor

Edit: Надеюсь, сейчас ссылка работает. Если нет, просто погуглите. :)

Я не знаю лучшего метода для вычисления диаметра, кроме всех кратчайших путей, но Mathematica использует следующее приближение для PseudoDiameter:

• Геодезический граф - это кратчайший путь между двумя вершинами графа. В диаметр графика самый длинный возможная длина всего графа геодезические графа. PseudoDiameter находит приблизительный диаметр графика. Он работает, запустив из вершины u, и находит вершину v что дальше всего от вас. Эта процесс повторяется, рассматривая v как новую начальную вершину и заканчивается когда расстояние графика больше не увеличивается. Вершина из последнего набор уровней с наименьшим степень выбрана в качестве окончательной начальная вершина u, а обход сделано, чтобы увидеть, может ли расстояние графика быть увеличенным. Это расстояние графа принимается за псевдо-диаметр.

http://reference.wolfram.com/mathematica/GraphUtilities/ref/PseudoDiameter.html

Править Я снова восстанавливаю удаление, просто чтобы продолжить комментировать. У меня есть несколько комментариев к алгоритму Джонсона под этим ответом. - Аарон

Мой оригинальный комментарий : Мне тоже интересно узнать об этой проблеме, но ответа нет. Кажется, он связан с Minimum Spanning Tree , подграфом, соединяющим все вершины, но имеющим наименьшее количество (или наименьший вес) ребер. Это старая проблема с рядом алгоритмов; некоторые из них кажутся довольно простыми в реализации.

Сначала я надеялся, что диаметр станет очевидным после того, как будет найден MST, но сейчас я теряю надежду :-( Возможно, MST можно использовать для размещения разумного верхнего привязанный к диаметру, который можно использовать для ускорения поиска фактического диаметра?

Вот некоторые мысли о том, что лучше, чем все пары кратчайших путей на неориентированном графе, хотя я не уверен, насколько это будет улучшено.

Вот подпрограмма, которая найдет расстояние D между двумя вершинами, если оно есть. Выберите произвольную вершину x и вычислите M[x] = максимальное расстояние от x до любой другой вершины (используя любой алгоритм кратчайшего пути из одного источника). Если M[x] >= D, то x - один из наших узлов, а другой легко найти. Однако, если M[x] < D, то ни одна из искомых конечных точек не может быть меньше расстояния D - M[x] от x (потому что существуют пути от этого узла до всех остальных узлов, через x, расстояния < D). Так что найдите все вершины расстояния меньше чем D-M[x] от x и пометьте их как плохие. Выберите новый x, на этот раз убедившись, что мы избегаем всех узлов, помеченных как плохие, и повторите. Будем надеяться, что мы пометим много узлов как плохие, так что нам придется делать намного меньше, чем |V| вычислений кратчайшего пути.

Теперь нам просто нужно установить D=diam(G) и запустить процедуру, описанную выше. Мы не знаем, что такое diam(G), но можем получить для него довольно узкий диапазон, как для любого x, M[x] <= diam(G) <= 2M[x]. Выберите несколько x для начала, вычислите M[x] для каждого, и в результате вычислите верхнюю и нижнюю границы диаметра(G). Затем мы можем выполнить двоичный поиск в результирующем диапазоне, используя вышеприведенную процедуру для поиска пути угадываемой длины, если таковой имеется.

Конечно, это только неориентированный поиск. Думаю, аналогичную схему можно сделать и с направленными графами. Плохими узлами являются те, которые могут достигать x менее чем в D-M[x], а верхняя граница на diam(G) не работает, поэтому вам понадобится больший диапазон бинарного поиска.

Я действительно сомневаюсь, что существует какой-нибудь метод поиска самого длинного короткого пути без необходимости использовать какой-нибудь алгоритм нахождения кратчайшего пути из всех пар (поиск кратчайшего пути из одного источника многократно, в наихудшем случае, делает все пары).

'Diameter' (Диаметр) становится трудно определить в терминах 'самый длинный путь', если граф не является деревом или DAG (DAG). Самый длинный путь может быть бесконечным, если на графе есть циклы. Следовательно, простой обход графа не может дать самый длинный путь по всем вершинам. Поскольку вы уже заявляли, что ваш граф не обязательно ациклический, и вас интересует "самый длинный короткий" путь, то, похоже, не существует никакого способа избежать нахождения самого короткого пути для всех узлов. Использование алгоритма Джонсона, как предложил Агор, наверное, лучше всего подходит для этого.

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

Грязный метод:

Мы знаем, что для графика G(V,E) с |V|=n и |E|=m, алгоритм Дийкстры выполняется в O(m+nlogn), и это для одного исходника. Для решения проблемы всех пар необходимо запустить Dijkstra для каждого узла в качестве отправной точки.

Однако, если у вас много машин, вы можете легко распараллелить этот процесс.

Этот метод проще всего реализовать, определенно не очень хорошо.

] Простите, если мой ответ неверен с точки зрения синтаксиса, но мой курс "Алгоритм" был недавно (и не на английском). [

]Если я правильно понимаю вашу проблему, вы хотите знать, до какого наибольшего числа вы можете сосчитать, начав с узла A и достигнув узла B без "втягивания" ваших шагов. Если это так, то я представляю ваш график как ациклический (опция "циклический" приходит позже). [

] Прежде всего, верхняя граница - это количество рёбер. Как я вижу, дело в следующем: возьмите один узел, создайте дерево, где узел находится в корне, и каждый последующий узел, до которого вы можете дотянуться, находится на следующем уровне. Высота дерева, которое вы строите - это диаметр, а листья - это узлы, которые находятся на этом расстоянии. Если это расстояние = количество ребер, то вы закончили. Если нет, то выберите другой узел и повторите.[

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

] Относительно цикличности графа - как отмечали другие, это может привести к бесконечным циклам. Способом избавиться от них может быть "исключение" узлов, принадлежащих циклу, и добавление самого длинного пути между ними в качестве значения, которое вы получите, войдя в цикл и выйдя из него, коснется каждой узловой точки только один раз. [

] Теперь, как я уже говорил, этот метод очень легко может быть таким же, как и при использовании кратчайшего пути "all-paires". В худшем случае сложность, безусловно, одинакова, и не может быть иначе. [

Один из способов получить оценку этого числа - начать со случайной точки и сделать алгоритм широты "захвата", пометив кратчайшее расстояние до каждого узла. Самое большое расстояние здесь - ваша оценка.

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

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

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

Не уверен, подходит ли он для счёта, но интересно:

HADI: Быстрая оценка диаметра и добыча в массивных графиках с Хадуп

U. Канг, К. Цуракакис, А. П. Аппель, К. Фалутсос, Я. Лесковец, "HADI: Быстрая оценка диаметра и горная добыча в массивных графиках с Хадупом", CMU ML Tech Report CMU-ML-08-117, 2008.