Floyd-Warshall 알고리즘

1. 플로이드-워셜(Floyd-Warshall) 알고리즘이란?

모든 최단 경로를 구하는 알고리즘

다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘 (S.S.S.P - Single Source Shortest Path) 이었다면, 플로이드-워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 알고리즘이다.

플로이드 워셜 알고리즘은 단계마다 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 하지만 매 단계마다 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다.
<-> 다익스트라의 경우 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다. 이후 해당 노드를 거쳐가는 경로를 확인하며 최단 거리 테이블을 갱신하는 방식으로 동작한다.

플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다.(모든 지점에서 다른 모든 지점까지의 최단 거리를 저장해야 하기 때문이다.)
<-> 다익스트라는 한 지점에서 다른 지점까지의 최단 거리이기 때문에 1차원 리스트에 저장한다.

플로이드 워셜 알고리즘은 DP 알고리즘에 속한다. 왜냐하면 만약 노드 개수가 N개라고 할 때, N번 만큼의 단계를 반복하며 점화식에 맞게 2차원 리스트를 갱신하기 때문에 DP라고 볼수 있다.
<-> 다익스트라는 그리디 알고리즘에 속한다고 볼 수 있다.

2. 플로이드-워셜 알고리즘의 과정

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

초기 그래프를 인접행렬로 나태내면 다음과 같다. INF는 해당 노드에서 특정 노드까지 가는 길이 없다는 뜻이다.

1	2	3	4	5
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

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

- Round 1 : 1번 노드에서 새로운 중간 노드로 설정

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

1	2	3	4	5
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

- Round 2 : 2번 노드를 새로운 중간 노드로 설정

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

1	2	3	4	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

이런 과정으로 5번 노드를 중간 노드로 선정하는 라운드까지 모두 거치면 행렬에는 모든 노드 간 최단 거리가 들어가게 된다.

3. 구현

플로이드-워셜 알고리즘은 시간 복잡도가 $O(n^3)$으로, 그래프의 크기가 작을 때 사용할 수 있다.
각 라운드 별로 중간 노드가 될 노드 번호를 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] = Main.min(dist[i][j], dist[i][k]+dist[k][j]);
        }
    }
}

Ref.

• ChanBLOG-알고리즘-플로이드-워셜(Floyd-Warshall) 알고리즘
• kdb.velog-[알고리즘] 플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm)