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

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

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

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

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

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

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