플로이드 워셜 알고리즘
플로이드 워셜(Floyd Warshall)
플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우에 사용할 수 있는 경우이다. 다익스트라 알고리즘에서는 한 지점에서 다른 모든 지점까지의 최단거리인 반면, 플로이드 워셜은 모든 지점 to 모드 지점인 것이다.
플로이드 워셜 알고리즘은 2차원 리스트에 최단 거리 정보를 저장한다. 노드의 개수가 N 개일 때 알고리즘상으로 N 번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐가는 모든 경로를 고려한다. 따라서 총 시간 복잡도는 O(N^3)이다.
- 플로이드 워셜 알고리즘을 사용해야 하는지에 대한 판단 기준
- 가중치 방향 그래프가 주어진다.
- A -> K -> B 이런식으로 어디를 거쳐간다.
- 시간 복잡도가 O(N^3) 이므로 N 의 범위 값이 500 이하여야 한다. (1초 기준)
플로이드 워셜 알고리즘 역시 다이나믹 프로그래밍에 속하므로 점화식이 중요한데 다음과 같다.
$$D(ab) = Min(D(ab), D(ak) + D(kb))$$
a 에서 b 로 가는 비용 = Min(기존에 저장된 a 에서 b 로 가는 비용 vs a 에서 k 를 거쳐 b 로 가는 비용) 이라고 나타낼 수 있다.
플로이드 워셜 알고리즘에서는 INF(무한의 값을 의미하는 상수) 를 초기화할 때 Integer.MAX_VALUE 로 초기화하면 안된다. D(ak) + D(kb) 이 부분을 수행할 때 MAX_VALUE 를 넘어가게되면 INTEGER.MIN_VALUE 에 가까운 값이 배열에 들어가게 되기 때문이다.
private static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억을 설정구현
다익스트라 알고리즘과 마찬가지로 플로이드 워셜 알고리즘은 최단 경로(Shortest Path)를 해결하기 위한 알고리즘으로 도로, 길찾기 문제에 주로 사용되며, 가중치 그래프가 주어진다. 만약, 문제에서 a 에서 k 를 거쳐 b 로 간다라는 내용이 존재한다면 플로이드 워셜 알고리즘을 사용하여 해결해야하는 문제일 가능성이 높다.
// 플로이드 워셜 알고리즘 : 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 할 때 사용
public class Main {
private static final int INF = (int) 1e9; // 다익스트라 알고리즘과는 달리 여기서는 Integer.MAX_VALUE 로 초기화하면 안된다.
private static int n; // 노드의 개수
private static int m; // 간선의 개수
// 인접 행렬 방식(Adjacency Matrix)
private static int[][] graph = new int[501][501]; // 노드의 개수는 최대 500 이라 가정
public static void main(String[] args) {
input();
floydwarshall();
output();
}
private static void input() {
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 a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
if (a == b) {
graph[a][b] = 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;
}
}
private static void floydwarshall() {
// 점화식에 따라 플로이드 워셜 알고리즘을 수행
for (int k = 1; k <= n; k++) {
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]);
}
}
}
}
private static void output() {
// 수행된 결과를 출력
for (int a = 1; a <= n; a++) {
for (int b = 1; b <= n; b++) {
// 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if (graph[a][b] == INF) {
System.out.print("INFINITY");
}
// 도달할 수 있는 경우 거리를 출력
else {
System.out.print(graph[a][b] + " ");
}
}
System.out.println();
}
}
}