플로이드-워셜 알고리즘 Swift

플로이드-워셜 알고리즘

그래프에서 최단거리를 구할때, 여러가지 알고리즘이 있고, 우리는 선택할 수 있다.

플로이드-워셜 알고리즘은 주어진 모든 노드쌍의 최단거리를 구하는 알고리즘이다.

이 알고리즘은 다익스트라와는 다르게 음의 가중치가 있는 그래프에서도 사용이 가능하며, 시간복잡도는 O(N^3)이다.

 

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

이 알고리즘은 노드 a에서 b까지 가는 최단거리를 구하기 위해, 두 노드 사이의 중간노드인 m을 이용하여 구한다.

m을통해 a에서 m까지의 최단거리와 m에서 b까지의 최단거리를 구하고 더하면 a에서 b까지의 최단거리가 된다.

그래프의 모든 노드를 중간노드로 설정해주며, 최단거리를 구해내간다.

 

아래 그래프로 플로이드 워셜 알고리즘을 이용해 최단거리를 구해보자.

 

이 그래프를 인접행렬로 나타내면 다음과 같다.

arr[i][j] : i에서 j로 가는 최단거리, INF: 연결되지않음

	A	B	C	D	E
A	0	5	1	INF	INF
B	5	0	2	1	4
C	1	2	0	4	INF
D	INF	1	4	0	2
E	INF	4	INF	2	0

 

주어진 모든 노드들을 중간노드로 설정하며 최단거리를 구해줄 것이다.

노드 i와 j사이의 중간노드 m을 설정한다면

arr[i][j] = arr[i][m] + arr[m][j]가 될것이고,

먼저 저장된 arr[i][j]와 arr[i][m] + arr[m][j]의 값을 비교하여 더 작은값을 넣는다.

 

1. 중간노드 : A

	A	B	C	D	E
A	0	5	1	INF	INF
B	5	0	2	1	4
C	1	2	0	4	INF
D	INF	1	4	0	2
E	INF	4	INF	2	0

 

중간노드 A로 설정시 갱신되는 최단거리가 없다.

 

2. 중간노드: B

	A	B	C	D	E
A	0	5	1	6	9
B	5	0	2	1	4
C	1	2	0	3	6
D	6	1	3	0	2
E	9	4	6	2	0

 

중간노드를 B로 설정하면 위와 같이 최단거리값이 갱신된다.

이는 노드 i에서 j로갈때의 중간노드 m : arr[i][j] > arr[i][m] + arr[m][j]이 성립한다는것이다.

 

3. 중간노드: C

	A	B	C	D	E
A	0	3	1	4	7
B	3	0	2	1	4
C	1	2	0	3	6
D	4	1	3	0	2
E	7	4	6	2	0

중간노드를 C로 설정하면 위와 같이 최단거리값이 갱신된다.

 

이렇게 그래프의 모든 노드를 중간노드로 하나씩 설정해주며 최단거리를 갱신하면 모든 쌍의 최단거리 배열이 완성된다.

이를 코드로 구현해보자.

import Foundation

// 그래프의 인접행렬
var graph = [
    [0, 5, 1, 1000000, 1000000],
    [5, 0, 2, 1, 4],
    [1, 2, 0, 4, 1000000],
    [1000000, 1, 4, 0, 2],
    [1000000, 4, 1000000, 2, 0]
]

// 플로이드-워셜 알고리즘
// 모든 노드를 중간노드로 설정해보고, 노드 i에서 j 사이 중간노드 m이라면
// arr[i][j] > arr[i][m] + arr[m][j]이라면 값 갱신
for m in 0..<5 {
    for i in 0..<5 {
        for j in 0..<5 {
            graph[i][j] = min(graph[i][j], graph[i][m] + graph[m][j])
        }
    }
}

 

결과:

// 결과
0 3 1 4 6
3 0 2 1 3
1 2 0 3 5
4 1 3 0 2
6 3 5 2 0