이번에는 플로이드 워셜에 대해서 정리하고, 문제를 기준으로 이해해보자.

위 문제의 예제인 아래 입력을 기준으로 설명해보도록 하겠다.

5
14
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
3 5 10
3 1 8
1 4 2
5 1 7
3 4 2
5 2 4

플로이드 워셜 알고리즘?

플로이드 워셜은 모든 노드 간의 최단경로를 구할 때 사용되는 알고리즘이다.

플로이드 워셜 3중 for문을 이용해서 구현할 수 있다.

우선 예제를 기준으로 표현해보자면 아래와 같다.

예제에서 나온 중복되는 경로에서의 큰 값은 제외하고 인접행렬을 만들었을 때 오른쪽과 같이 만들어 낼 수 있다.

여기서 INF는 Infinity의 줄임말로 해당 노드로 이동할 수 있는 방법이 없음을 표현한 것이다.

플로이드 워셜 알고리즘은 위와 같은 상황에서 다른 노드를 통해 해당 노드로 접근하는 경로를 찾아낼 수 있다.

구현

위에서 언급 했던 것 처럼 플로이드 워셜 알고리즘은 3중 for문을 이용한다.

private static void floydWarshall() {
    for (int i = 1; i <= N; i++) { // 중간
        for (int j = 1; j <= N; j++) { // 처음
            for (int k = 1; k <= N; k++) { // 끝
		            if (j == k) continue;
                if (graph[j][k] > graph[j][i] + graph[i][k]) {
                    graph[j][k] = graph[j][i] + graph[i][k];
                }
            }
        }
    }
}