플로이드 워셜 알고리즘이란?
-
- 모든 노드 간의 최단 경로를 구하는 알고리즘
- 벨만 포드 알고리즘과 동일하게 음수 간선이 있어도 최단 경로를 구할 수 있습니다.
- 음수 사이클이 존재할 때는 사용하지 못합니다.
- 알고리즘 복잡도 : O(V^3)
- 모든 경로를 구하다보니 V * V(노드 수,Vertex) 만큼의 메모리가 필요합니다.
플로이드 워셜 알고리즘 흐름
- 요약
- 임의의 노드 s에서 e까지 가는 데 걸리는 최단거리를 구하기 위해, s와 e 사이의 노드인 m에 대해 s에서 m까지 가는 데 걸리는 최단거리와 m에서 e까지 가는 데 걸리는 최단거리를 이용합니다.
- 우선 모든 노드들을 돌면서 최단경로 메모리에 직접적으로 연결되어있는 노드라면 가중치를, 아니라면 INF로 초기화합니다.
- 쉽게 말해서 모든 노드돌면서 연결된 인접한 노드들은 간선 가중치로 업데이트하고 나머지는 INF로 업데이트 해줍니다.
- 모든 노드를 돌면서, 한 노드(s)에서 다른 노드(e)로 가기 위한 경로를 구하기 위해서, s와 e 사이의 모든 노드 m에 대해, 현재 메모리에 저장되어 있는 s -> e까지의 경로 값과 s -> m + m -> e 값을 비교하여 s->e까지의 경로 값을 둘 중 작은 값으로 업데이트 합니다.
- dist[s][e] 값과 dist[s][m] + dist[m][e] 값을 비교하고 둘 중 더 작은 값으로 dist[s][e]값을 갱신합니다.
- 경로를 전부 업데이트 한 후, 음수 사이클이 존재하는지 확인하기 위해 자기 자신으로 가능 경로 상에 음수가 있는지 확인합니다.
- dist[s][s] 값이 음수인지 확인합니다.
플로이드 워셜 알고리즘 구현
/**
* 플로이드 워셜 알고리즘 (Floyd_Warshall)
* - 모든 경로에서 모든 경로까지의 최단경로를 구하는 알고리즘
* - 음수 간선이 있는 경우에도 사용가능
* - 시간 복잡도 : O(V^3)
*
* 알고리즘 흐름
* 1. 모든 노드를 돌면서 모든 노드로의 이동 경로 가중치를 업데이트
* 1-1 직접적으로 연결되어있으면 가중치로 업데이트 / 연결되어있지 않으면 INF로 업데이트
* 2. 특정 노드(m)를 거쳐서 이동하는 경로를 삼중 for문을 이용하여 업데이트
* 2-1 dist[s][e] 와 dist[s][m] + dist[m][e]의 값을 비교한 후 작은 값으로 dist[s][e]업데이트
* 2-2 dist[s][m]나 dist[m][e]가 INF라면 연결이 안되어있다는 소리니 통과한다.
* 3. 모든 업데이트가 완료된 후, 자기자신의 경로값에 음수값이 있다면 음수 사이클이 있다는 소리니 알고리즘을 중지한다.
*/
public class Floyd_Warshall {
static int[][] dist;
static final int INF = 1000000000;
public static void floydWarshall(int vertex, int edge, int[][] data, int start) {
// 최단 경로를 저장할 배열 생성
dist = new int[vertex + 1][vertex + 1];
// 초기화
for (int i = 1; i < vertex + 1; i++) {
for (int j = 1; j < vertex + 1; j++) {
// 대각선이 아닌 경우(자기자신 경로), 처음에는 모두 INF 값으로 초기화
if (i != j) {
dist[i][j] = INF;
}
}
}
for (int i = 0; i < edge; i++) {
// 인접한 노드에서 바로 갈 수 있는 경로의 가중치 업데이트
dist[data[i][0]][data[i][1]] = data[i][2];
}
for (int m = 1; m < vertex + 1; m++) {
// i -> j (k를 거쳐서 가는 경우가 짧을 때 업데이트)
for (int s = 1; s < vertex + 1; s++) {
for (int e = 1; e < vertex + 1; e++) {
if (dist[s][m] != INF && dist[m][e] != INF) {
dist[s][e] = Math.min(dist[s][e], dist[s][m] + dist[m][e]);
}
}
}
}
for (int i = 1; i < vertex + 1; i++) {
if (dist[i][i] < 0) {
System.out.println("음수 사이클이 존재합니다.");
return;
}
}
}
}
댓글