플로이드 워셜(Floyd-Warshall) 알고리즘

1. 플로이드 워셜(Floyd-Warshall)

 이 알고리즘은 동적 계획법의 한 예로, 로버트 플로이드가 1962년에 현재 알려진 형태로 발표했다고 한다. 하지만 본질적으로는 1956년 클레이니 알고리즘, 1959년 버나드 로이의 알고리즘, 1962년 스티븐 워셜 알고리즘과 밀접한 관련이 있다. 따라서 이 알고리즘은 플로이드-워셜 알고리즘, 로이-워셜 알고리즘, 로이-플로이드 알고리즘, 또는 WFI 알고리즘으로 불린다고 한다.

 

플로이드 워셜 알고리즘은 "모든 최단 경로를 구하는 알고리즘"이다.

한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있다.

그러나 플로이드 워셜 알고리즘의 시간 복잡도는 O(n^3)이다.

즉, 그래프의 크기가 작아 세제곱 시간 알고리즘을 적용해도 문제가 풀리는 경우에만 사용이 가능하다.

 

 

2. 과정

 모든 노드 간의 최단거리를 구해야 하므로 2차원 인접 행렬을 구성한다. 알고리즘은 여러 라운드로 구성되며, 라운드마다 각 경로에서 새로운 중간 노드로 사용할 수 있는 노드를 선택하고, 더 짧은 길이를 선택해 줄이는 과정을 반복한다.

 

 

1. 라운드 0 - 초기 그래프를 인접행렬로 나타내면 다음과 같다

INF는 해당 노드에서 특정 노드까지 가는 길이 없다는 것을 의미한다.

0	5	INF	9	1
5	0	2	INF	INF
INF	2	0	7	INF
9	INF	7	0	2
1	INF	INF	2	0

 

 

2. 라운드 1 - 1번 노드를 새로운 중간 노드로 설정

이 그래프는 1번부터 5번 노드까지 존재하므로 총 다섯번의 과정을 거친다. 즉, 모든 노드들을 중간 노드로 선정하는 과정을 각 라운드마다 거친다. 예를 들어 라운드 2는 2번 노드가 중간 노드이며, 라운드 3은 3번 노드가 중간 노드가 될 것이다.

 

2번에서 4번으로 가는 길은 원래 없었으나, 1번 노드를 중간 노드로 선정할 경우 2-1-4 (길이 5 + 9 = 14)로 갈 수 있게 된다.

업데이트 된 길이는 Bold체 + 빨간색으로 표시한다.

0	5	INF	9	1
5	0	2	14	6
INF	2	0	7	INF
9	14	7	0	2
1	6	INF	2	0

 

 

3. 라운드 2 - 2번 노드를 새로운 중간 노드로 설정

1번 - 3번 노드를 잇는 경로, 3번 - 5번 노드를 잇는 경로가 새로 생기게 된다.

0	5	7	9	1
5	0	2	14	6
7	2	0	7	8
9	14	7	0	2
1	6	8	2	0

... 이후 반복 ...

 

이러한 과정을 거쳐 다섯 번째 라운드까지 진행되게 되면, 행렬에는 모든 노드 간의 최단 거리가 들어가게 된다.

 

 

3. 구현

• adj에 저장된 인접 행렬의 값을 활용하여 최단 거리 배열인 dist 배열을 초기화한다.

for(int i = 1; i<=n; i++){
    for(int j =1; j<=n; j++){
        if (i == j) dist[i][j] = 0;
        else if (adj[i][j]) dist[i][j] = adj[i][j];
        else dist[i][j] = INF;
    }
}

 

• 각 라운드별로 중간 노드가 될 노드 번호를 for문 가장 바깥의 k로 삼는다. 내부 이중 for문에는 i, j를 통해 각 노드별 모든 거리를 살펴보면서 k를 중간 노드로 삼을 때와 아닐 때의 값을 비교해 더 작은 값으로 업데이트 시킨다.

for(int k = 1; k<= n; k++){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j<=n; j++){
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
        }
    }
}

 

 

4. 연관 문제

• 1389번: 케빈 베이컨의 6단계 법칙 - https://www.acmicpc.net/problem/1389
• 11404번: 플로이드 - https://www.acmicpc.net/problem/11404

 

 

5. 참고자료

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

플로이드-워셜 알고리즘 - 위키백과, 우리 모두의 백과사전

https://chanhuiseok.github.io/posts/algo-50/

알고리즘 - 플로이드-워셜(Floyd-Warshall) 알고리즘

https://velog.io/@kimdukbae/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Floyd-Warshall-Algorithm

[알고리즘] 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)