플로이드 와샬(Floyd Warshall)알고리즘
다익스트라 알고리즘 : 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘
플로이드 와샬 알고리즘 : '모든 정점'에서 '모든 정점'으로의 최단 경로'를 구하고 싶을때 사용하는 알고리즘
다익스트라 알고리즘은 가장 적은 빕용을 하나씩 선택해야 했다면 플로이드 와샬 알고리즘은 기본적으로 '거쳐가는 정점'을 기준으로 알고리즘을 수행한다는 점이 특징이 있습니다.
이차원 배열로 표현하면 다음과 같다.
| 정점 | 1 | 2 | 3 | 4 |
| 1 | 0 | 5 | 무한 | 8 |
| 2 | 7 | 0 | 9 | 무한 |
| 3 | 2 | 무한 | 0 | 4 |
| 4 | 무한 | 무한 | 3 | 0 |
이 테이블은 1->1, 1->2, 1->3... 으로 현재까지 계산된 최소 비용입니다.
이러한 2차원 배열을 반복적으로 갱신하며 모든 최소 비용을 구할때까지 반복합니다. 반복의 기준은 '거쳐가는 정점'인 것입니다.
노드 1을 거쳐가는 경우 표
| 정점 | 1 | 2 | 3 | 4 |
| 1 | 0 | 5 | 무한 | 8 |
| 2 | 7 | 0 | 9 | 15 |
| 3 | 2 | 7 | 0 | 4 |
| 4 | 무한 | 무한 | 3 | 0 |
노드 1을 거쳐가는 경우는 위와 같이 6가지 공간만을 갱신해주면 됩니다.
이 때 다음 두 식을 비교하며 반복합니다.
X에서 Y로 가는 최소 비용 VS X에서 노드 1로 가는 비용 + 노드 1에서 Y로 가는 비용
즉 1을 거쳐서 가는 경우가 더 빠른 경우가 존재한다면 빠른 경우로 최소 비용을 계산하는 것입니다.
예시로 D[2,3]의 값은 D[2,3]=9와 (D[2,1] + D[1,3]) = 7+무한과 비교하게 되며 D[2,3]의 값이 작기때문에 교체되지 않습니다.
D[2,4]의 값 무한과 (D[2,1] + D[1,4]) = 7 + 8 = 15로 (D[2,1] + D[1,4])의 값이 작기때문에 무한->15로 교체됩니다.
노드2를 거쳐가는 경우
| 정점 | 1 | 2 | 3 | 4 |
| 1 | 0 | 5 | 14 | 8 |
| 2 | 7 | 0 | 9 | 15 |
| 3 | 2 | 7 | 0 | 4 |
| 4 | 무한 | 무한 | 3 | 0 |
노드 2를 거쳐가는 경우도 마찬가지로 6가지 공간을 갱신해주면 됩니다.
D[1,3] = 무한 (D[1,2] + D[2,3]) = 5 + 9 = 14로 (D[1,2] + D[2,3]) = 14로 값이 무한 -> 14로 교체됩니다.
위와 같은 방식으로 노드3을 거쳐가는 경우 노드4를 거쳐가는 경우를 진행하면 결과는 다음과 같습니다.
| 정점 | 1 | 2 | 3 | 4 |
| 1 | 0 | 5 | 11 | 8 |
| 2 | 7 | 0 | 9 | 13 |
| 3 | 2 | 7 | 0 | 4 |
| 4 | 5 | 10 | 3 | 0 |
- 2차원 테이블에 모든 노드에서 다른 모든 노드로 이동하는 최단 거리 정보를 기록할 수 있습니다.
- 실제로 2차원 테이블에 있는 값을 점화식에 따라서 갱신한다는 점에서 다이나믹 프로그래밍 유형에 속합니다.
- 점화식에 맞게 삼중반복문을 이용해서 2차원 테이블을 갱신하며 O(n^3) 시간복잡도를 가집니다.
- 노드의 갯수가 적은 상황에서 유용하다. 노드와 간선의 갯수가 많다면 다익스트라 알고리즘이 적합합니다.
- 문제에서 노드의 갯수가 적다면 플로이드 워셜 알고리즘으로 풀 수 있는 문제인지 의심해봐야한다
Python
# 무한을 의미하는 값으로 10억을 설정
INF = int(1e9)
#노드의 개수 및 간선의 개수를 입력받기
n = int(input())
m = int(input())
# 2차원 리스트(그래프 표현)를 만들고
# 무한으로 초기화 1번부터 출발한다고 가정
graph = [[INF] * (n+1) for _ in range(n+1)]
# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for a in range(1, n+1):
for b in range(1, n+1):
if a == b:
graph[a][b] = 0
# 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
for _ in range(m):
# A에서 B로 가는 비용을 C라고 설정
a, b, c = map(int, input().split())
graph[a][b] = c
# 점화식에 따라 플로이드 워셜 알고리즘을 수행
for k in range(1, n+1):
for a in range(1, n+1):
for b in range(1, n+1):
graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
# 수행된 결과를 출력
for a in range(1, n+1):
for b in range(1, n+1):
if graph[a][b] == INF:
print("INFINITY", end=" ")
# 도달할 수 있는 경우 거리를 출력
else:
print(graph[a][b], end=" ")
print()
Java
public class FloydWarshall {
private static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억을 의미
// 노드의 개수 (N), 간선의 개수 (M)
// 노드의 개수는 최대 500개라고 가정
private static int n, m;
// 2차원 배열(그래프 표현)를 만들기
private static int[][] graph = new int[501][501];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
// 최단 거리 테이블을 모두 무한으로 초기화
for (int i = 0; i < 501; i++) {
Arrays.fill(graph[i], INF);
}
// 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
for (int i = 1; i <= n; i++) {
graph[i][i] = 0;
}
// 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화
for (int i = 0; i < m; i++) {
// A에서 B로 가는 비용은 C라고 설정
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
graph[a][b] = c;
}
// 점화식에 따라 플로이드 워셜 알고리즘을 수행
for (int k = 1; k <= n; k++) {
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; a++) {
graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]);
}
}
}
// 수행된 결과를 출력
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n ; b++) {
// 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if (graph[a][b] == INF) {
System.out.print("INFINITY ");
continue;
}
System.out.print(graph[a][b] + " ");
}
System.out.println();
}
}
}
위에 '문제에서 노드의 갯수가 적다면 플로이드 워셜 알고리즘으로 풀 수 있는 문제인지 의심해봐야한다' 라고 작성해놓는데 예시를 살펴보겠습니다.
백준11404번. 플로이드
문제를 보면 노드의 갯수가 다른 문제들과 비교해보면 작은수로 제한되어있다. 이 문제는 문제 이름 자체가 '플로이드'이지만 플로이드 와샬 알고리즘으로 풀 수 있는지 생각해봐야한다.
n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.
모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.