(Java) 플로이드-워셜 알고리즘 (feat. 백준 11404번 문제 플로이드)

정의

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

시간복잡도는 O(N^3)이다. 음의 가중치를 가지는 그래프에서도 사용할 수 있다는 점이 다익스트라 알고리즘과 다른 특징.

 

 

 

설명

임의의 노드 Start 에서 End까지 가는데 최단 거리를 구하기 위해 Start와 End 사이의 노드인 Mid에 대해 Start에서부터 Mid까지의 최단 거리와 Mid에서부터 End까지의 최단 거리를 전부 고려하는 것이 플로이드-워셜 알고리즘이다.

 

방법은 다음과 같다.

시작 노드와 도착 노드의 가중치를 담은 2차원 배열 arr,

s는 start 노드의 약자, e는 end 노드의 약자, m는 middle 노드의 약자라고 할 때,

if(arr[s][e] > arr[s][m] + arr[m][e]) {
	arr[s][e] = arr[s][m] + arr[m][e]
}

 

만약 s 노드에서 e 노드로 가는 가중치보다 m을 통해서 가는 가중치가 더 낮다면 해당 2차원 배열의 값을 낮은 값으로 바꾼다. 이것을 모든 노드를 순회하며 실행하면 되는 것이다.

 

 

 

 

예시를 보며 자세히 알아보자.

백준 11404번 문제 플로이드이다.

https://www.acmicpc.net/problem/11404

 

문제를 간단하게 설명하면 도시와 버스가 존재하는데 모든 도시의 쌍(A, B)에 대해 A에서 B로 이동할 때 최소 비용을 구하는 문제이다. 도시의 개수 N, 버스의 개수 M이 주어지고, 각 버스마다 시작 도시와 도착 도시, 한 번 타는데 필요한 비용이 입력 값으로 주어진다.

public class Main {
    static final int INF = 1_000_000_000;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int NArr[][] = new int[N+1][N+1];
        for(int i = 1; i<=N; i++) {
            for(int j = 1; j <= N; j++) {
                NArr[i][j] = i != j ? INF : 0;
            }
        }
        int M = Integer.parseInt(br.readLine());

        for(int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            NArr[start][end] = Math.min(NArr[start][end], cost);
        }

        for(int m = 1; m<=N; m++) {
            for(int s = 1; s <= N; s++) {
                for(int e = 1; e <= N; e++) {
                    if(NArr[s][e] > NArr[s][m] + NArr[m][e]) {
                        NArr[s][e] = NArr[s][m] + NArr[m][e];
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j<= N; j++) {
                int ans = NArr[i][j] == INF ? 0 : NArr[i][j];
                sb.append(ans+ " ");
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }
}

 

 

 

 

플로이드-워셜 알고리즘의 핵심 부분은 다음과 같은데

for(int m = 1; m<=N; m++) {
    for(int s = 1; s <= N; s++) {
        for(int e = 1; e <= N; e++) {
            if(NArr[s][e] > NArr[s][m] + NArr[m][e]) {
                NArr[s][e] = NArr[s][m] + NArr[m][e];
            }
        }
    }
}

 

시작 노드 s에서부터 도착 노드 e까지 이동하는데 필요한 비용이 중간 노드 m을 거쳐서 가는 비용보다 비싸다면 더 저렴한 비용으로 대체하는 코드이다. 여기서 중요한 부분은 3중 반복문의 순서인데 중간 노드 m이 가장 바깥 루프에 위치하도록 둬야한다는 것이다.

 

그 이유는 중간 노드 m을 통해 최단 경로가 계속 수정되어야 하는데, 시작 노드 s나 도착 노드 e가 가장 바깥 루프에 위치한다면 최단 경로가 누락될 수 있기 때문이다.

 

 

 

 

다음과 같은 예시가 있을 수 있다.

5개의 노드(1, 2, 3, 4, 5)가 있는 그래프를 고려해보자.

1 → 2 → 3 → 4 → 5 가 최단 경로일 때 시작 노드 s나 도착 노드 e가 가장 바깥 루프에 위치한다면

1 → 5를 처리할 때 2 → 3, 3 → 4, 4 → 5의 개별 경로들이 아직 최적화되지 않은 상태로 해당 경로 부분이 누락되게 된다.

 

그러므로 중간 노드가 가장 바깥 루프를 돌아야한다는 점을 명심하자.