[Algorithm] 플로이드-워셜(Floyd-Warshall)

플로이드-워셜(Floyd-Warshall)?

플로이드-워셜은 그래프에서 가능한 모든 노드 쌍에 대해 최단 거리를 구하는 알고리즘이다.

 

다익스트라 알고리즘과는 달리 모든 노드 쌍에 대해 최단 거리를 구하고, 음의 가중치를 가지는 그래프에서도 쓸 수 있다는 것이 특징이며 다익스트라보다 구현이 쉽다.

 

플로이드-워셜은 모든 지점에서 다른 모든 지점까지의 최단 거리를 저장해야하기 때문에 2차원 배열에 최단 거리 정보를 저장한다.

또한, DP의 특징을 가지고 있어서 노드의 개수(N)번 만큼의 단계를 반복하며 점화식에 맞게 2차원 배열을 갱신해나간다.

 

 

구현

설명

플로이드-워셜은 임의의 노드 s에서 e까지 가는데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와 m에서 e까지 가는 데 걸리는 최단거리를 이용한다.

 

점화식으로 표현하면 다음과 같다.

즉 간단하게 얘기하면 s에서 e로 바로 가는 길과 중간에 m을 거쳐 가는 길 중 더 가까운 곳으로 갱신하겠다는 말이다.

여기서 연결되지 않은 곳을 INF로 설정하게 되면 두 가지 상황이 발생한다.

1. 다른 곳을 거쳐서 연결되지 않은 곳으로 갈 수 있을 경우 그 값이 더 작은 값으로 갱신된다.
2. 연결되지 않은 곳을 거쳐가려해도 INF + x는 당연히 충분히 큰 값이기 때문에 다른 곳의 값이 이 값으로 갱신될 수 없다.

이렇게 되기 때문에 연결되지 않은 곳은 INF(언어에 따라 충분히 큰 값을 설정)로 초기화 시켜준다.

 

코드

public class PloydWarshall {

    private static final int INF = 1_000_000_000;

    public static void main(String[] args) {
        int[][] graph = {
                {0, 4, INF, 6},
                {3, 0, 7, INF},
                {5, INF, 0, 4},
                {INF, INF, 2, 0}};

        int n = 4;

        for (int m = 0; m < n; m++) {
            for (int s = 0; s < n; s++) {
                for (int e = 0; e < n; e++) {
                    graph[s][e] = Math.min(graph[s][e], graph[s][m] + graph[m][e]);
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(graph[i][j] + " ");
            }
            System.out.println();
        }
    }
}

0 4 8 6 
3 0 7 9 
5 9 0 4 
7 11 2 0

구현은 단순히 반복문을 3번 중첩시키면 되기 때문에 어렵지 않다. 여기서 유의할 점은 for문에서 가운데 노드(m)가 제일 위에 있어야 한다는 점이다.

또, 그래프에서 무한을 설정할 때 데이터 타입의 경곗값으로 설정하는 것을 주의해야한다.

예를 들어 위 코드에서 Integer.MAX_VALUE로 무한을 설정하면 overflow가 발생하여 -값이 나오게된다.

 

시간 복잡도

3중 반복문을 돌기 때문에 O(V^3)의 시간복잡도를 가진다. 또한 인접행렬의 형태를 가지기 때문에 O(V^2)의 공간 복잡도를 가지고 있다.