[java] 플로이드-와샬 알고리즘의 시간 복잡도
플로이드-와샬 알고리즘은 그래프의 모든 정점 간의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 다이나믹 프로그래밍의 개념을 기반으로 하고 있으며, 시간 복잡도는 O(N^3)입니다.
여기서 N은 정점의 개수를 나타냅니다. 알고리즘은 세 개의 중첩된 반복문을 사용하여 모든 정점 쌍에 대해 최단 경로를 계산합니다. 따라서 반복문을 실행하는 횟수는 정점 수에 비례하므로 O(N^3)의 시간 복잡도를 갖습니다.
이 알고리즘은 그래프의 인접 행렬로 표현된 경우에 효과적으로 동작합니다. 인접 행렬은 모든 정점 쌍 사이의 거리를 저장하는 2차원 배열로 표현되며, 초기에는 직접적인 간선이 없는 경우에는 무한대 값이 저장됩니다. 알고리즘의 핵심은 중간 정점을 거쳐가는 경로가 더 짧은지를 확인하고, 더 짧은 경로가 있는 경우 거리 값을 갱신하는 것입니다.
이러한 플로이드-와샬 알고리즘은 간단하면서도 효율적인 방법으로 모든 정점 간의 최단 경로를 찾을 수 있습니다. 따라서 대규모 그래프에서 유용하게 사용될 수 있습니다.