[JAVA/알고리즘] 플로이드-워셜 알고리즘 : 모든 쌍 최단 경로 탐색

안녕하세요

그래프 이론의 중요한 개념인 플로이드-워셜 알고리즘에 대해 글을 작성 해보겠습니다.

플로이드-워셜 알고리즘은 모든 쌍 최단 경로(All-Pairs Shortest Path) 문제를 해결하는데 사용 됩니다.

 

 

플로이드-워셜 알고리즘 개요

플로이드-워셜 알고리즘은 비용이 부여된 그래프에서 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘 입니다. 이 알고리즘은 동적 프로그래밍을 기반으로 하며, 그래프의 모든 정점들을 서로 연결하는 최단 경로의 비용 계산합니다.

 

알고리즘의 특징

• 범용성 : 양의 비용 뿐만 아니라 음의 비용이 있는 그래프에도 적용할 수 있습니다. 단 음의 반복되는 비용이 없어야 합니다.
• 구현의 단순성 : 세 개의 중첩 반복문만으로 구현할 수 있어, 알고리즘의 이해와 구현이 비교적 쉽습니다.

구현 예제

public class FloydWarshallAlgorithm {
    final static int INF = 99999; // 무한대를 나타내는 값

    public static void floydWarshall(int graph[][], int V) {
        int dist[][] = new int[V][V];
        int i, j, k;

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

        // 플로이드-워셜 알고리즘
        for (k = 0; k < V; k++) {
            for (i = 0; i < V; i++) {
                for (j = 0; j < V; j++) {
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }

        // 결과 출력
        printSolution(dist, V);
    }

    public static void printSolution(int dist[][], int V) {
        System.out.println("The following matrix shows the shortest distances between every pair of vertices");
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                if (dist[i][j] == INF)
                    System.out.print("INF ");
                else
                    System.out.print(dist[i][j] + "   ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int graph[][] = { {0, 5, INF, 10},
                          {INF, 0, 3, INF},
                          {INF, INF, 0, 1},
                          {INF, INF, INF, 0} };
        floydWarshall(graph, 4);
    }
}

코드 설명

• 초기 거리 행렬 설정 : 각 정점 간의 초기 거리를 나타내는 2차원 배열 'dist[][]' 를 만들고, 입력 그래프의 가중치 정보로 초기화 합니다.
• 플로이드-워셜 알고리즘 적용 : 각 정점 쌍에 대해, 모든 중간 정점을 거쳐가는 경우를 고려하여 최단 경로를 업데이트합니다.
• 최단 거리 행렬 출력 : 모든 정점 쌍 간의 최단 거리를 출력합니다.

 

성능 분석

• 시간 복잡도 : O(V³) 여기서 V는 정점의 수 입니다.
• 공간 복잡도 : O(V²), 2차원 배열을 사용하여 각 정점 쌍 간의 최단 거리를 저장합니다.

이 알고리즘은 그래프 이론 및 네트워크 라우팅과 같은 다양한 영역에서 중요한 응용을 가집니다.