Dijsktra 최악의 경우의 복잡도 시퀀스

Question

Dijsktras의 실제 복잡도는 Θ ((e + v) logv) 인 정규 힙으로 구현 된 Dijsktra 알고리즘에 대한 입력 시퀀스를 찾고 있습니다.

저는 Dijsktra를 구현하는 방법을 알고 있고 어떻게 작동하는지 알고 있습니다. 또한 가장 시간이 많이 걸리는 작업은 힙에 정점을 추가하고 정점의 거리를 변경하는 것입니다. 그러나 Dijkstra의 최악의 경우 입력이되는 그래프 (그래프 시퀀스)를 찾는 방법을 모르겠습니다.

최악의 경우의 복잡도에 대한 일련의 입력을 찾는 방법에 대한 일반적인 팁이 있다면 도움이 될 것입니다.

Answer 1

정점을 1에서 n까지 번호 매기고 정점 1에서 정점 n까지의 경로를 찾고 싶습니다. e[i][j]을 모서리 길이로하고 i과 j을 연결하십시오. 처음에는 e[1][2] = e[2][3] = ... = e[n - 1][n] = 1입니다. 이제 n - 2에서 1까지 정점을 반복합니다. 각 j의 번째 정점에서 [i + 2, n]에 e[i][j] = e[i][i + 1] + e[i + 1][j] + 1을 만듭니다.

이제 전체 그래프가 표시됩니다. 각 반복에서 dijkstra는 O(n) 정점을 업데이트하므로 O(n^2) = O(E) 작업이 O(log n)에서 작동합니다.

그래서 최종 점근선은 O(n log(n) + E log(n))