[java] 플로이드-와샬 알고리즘

04 Dec 2023

java

플로이드-와샬 알고리즘은 그래프에서 모든 정점 쌍 사이의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 동적 프로그래밍의 한 종류로, 그래프의 모든 정점에 대한 최단 경로를 찾기 위해 중간에 있는 정점을 하나씩 추가해가며 최단 경로를 갱신합니다.

알고리즘 설명

플로이드-와샬 알고리즘은 3중 반복문을 사용하여 그래프의 모든 간선에 대한 최단 경로를 찾습니다. 각 반복에서는 모든 정점 쌍에 대해 현재 정점까지의 경로와 현재 정점을 거쳐가는 새로운 경로를 비교하여 최단 경로를 갱신합니다.

public class FloydWarshall {
    public void floydWarshall(int[][] graph) {
        int V = graph.length;
        int[][] dist = new int[V][V];

        // 초기 거리 설정
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                dist[i][j] = graph[i][j];
            }
        }

        // 중간 정점을 하나씩 추가해가며 최단 경로 찾기
        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
    }
}

위의 예제는 플로이드-와샬 알고리즘의 Java 구현입니다. 입력으로 주어진 2차원 배열 graph는 그래프의 인접 행렬을 나타냅니다. dist 배열은 최단 경로의 길이를 저장하기 위한 배열로, 초기에는 graph의 값으로 초기화합니다.

시간 복잡도

플로이드-와샬 알고리즘의 시간 복잡도는 O(V^3)입니다. 여기서 V는 그래프의 정점의 수를 의미합니다. 이 알고리즘은 모든 정점 쌍에 대해 최단 경로를 찾기 때문에, 모든 정점에 대해 3중 반복문이 실행되는 것입니다.

결론

플로이드-와샬 알고리즘은 그래프에서 모든 정점 쌍 사이의 최단 경로를 찾는 강력한 알고리즘입니다. 동적 프로그래밍의 아이디어를 활용하여 이전의 최단 경로를 이용해 새로운 최단 경로를 찾는 방식으로 동작하며, 시간 복잡도는 O(V^3)입니다. 이 알고리즘은 네트워크 라우팅, 지리 정보 시스템 등 다양한 분야에서 활용됩니다.

참고 문헌:

GeeksforGeeks - Floyd Warshall Algorithm