그래프의 평균 최단 경로 길이 및 직경 알고리즘의 시간 복잡도에 차이가 있습니까?

Question

undirected, unweighted 그래프의 경우 평균 최단 경로 길이를 계산하는 알고리즘의 시간 복잡도와 그래프의 직경을 계산하는 알고리즘의 복잡성, 즉 두 개 사이의 가장 긴 최단 경로 정점?

Answer 1

Wikipedia에 따르면 그래프의 직경을 계산하려면 먼저 모든 쌍의 최단 경로를 찾아야합니다. 모든 쌍 최단 경로를 계산 한 후에 두 알고리즘 모두 O (V^2) 계산으로 축소되므로 계산 복잡도는 동일합니다.

Answer 2

아니요 둘 사이의 시간 복잡도에 차이가 없어야합니다.

가장 짧은 경로 인 algo를 조정하여 두 꼭지점 간의 가장 긴 경로를 찾을 수 있습니다.

Answer 3

나는이 주제에 관한 많은 문헌을 읽지 않았지만 나는 둘이 동일하다고 생각한다. 그러나 불일치가 있다면, 그래프의 직경을 계산하는 것이 점근적으로 빠를 것이라고 말할 수 있습니다.

내 알고리즘은 모두 V*(E+V*log(V))에서 실행되는 Dijkstra 알고리즘을 사용하여 모든 쌍 최단 경로를 계산하는 것입니다. 그런 다음이 모든 값에 대해 산술 평균을 취합니다. 나는 당신이 이것을 빠르게 할 수있는 방법을 보지 못합니다.

그러나 그래프의 직경을 계산할 때이 프로세스의 속도를 높이는 데 사용할 수있는 영리한 트릭이있을 수 있습니다. 그러나 상한선으로, 모든 쌍의 최단 경로를 통해 상향 점을 취하면 지름을 구할 수 있습니다.이 평균 직경은 평균 최단 경로 계산과 동일한 런타임 복잡성이 있습니다.