Есть ли разница в сложности времени для алгоритмов средней длины и диаметра пути для графа?

Question

Для неориентированного, невзвешенного графа, есть ли разница во временной сложности алгоритма для вычисления его средней длины кратчайшего пути против сложности алгоритма, который вычисляет диаметр графа, то есть самый длинный кратчайший путь между две вершины?

Answer 1

Согласно Википедии , для расчета диаметра графа сначала необходимо найти кратчайший путь из всех пар.После вычисления кратчайшего пути из всех пар оба алгоритма сводятся к вычислению O (V ^ 2), поэтому их сложности одинаковы.

Answer 2

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

Мой алгоритм для обоих будет вычислять кратчайший путь из всех пар с использованием алгоритма Дейкстры, который работает в V*(E+V*log(V)),Тогда для среднего вы бы взяли среднее арифметическое по всем этим значениям.Я не вижу способа, которым вы могли бы ускорить это.

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

Answer 3

Нет, не должно быть никакой разницы в сложности времени между ними.

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