플로이드-워셜 알고리즘
- 모든 정점 쌍 간 최단 경로를 찾는 알고리즘
- 3개의 중첩 for문을 사용하는 매우 단순한 알고리즘!
- 그래프의 두 정점 사이의 직접 연결된 경로가 있거나, 다른 정점 k를 경유하는 경로가 있을 경우, 둘 중 더 짧은 경로를 선택하는 방식
- 시간복잡도 : O(N^3)
동작 원리
1. 인접 행렬을 기반으로 모든 정점 간 최단 거리를 초기화. 인접하지 않은 경우는 무한대로 설정
2. 각 정점을 중간 노드로 설정해 두 정점 간 경로 갱신
3. 최종적으로 가장 짧은 경로를 도출
장점
- 메모리를 비교적 덜 차지함
- 음수 가중치가 있어도 적용할 수 있음
- 간단하고 직관적임
단점
- 시간복잡도가 급격히 증가하므로, 정점 수가 적을 때만 적용할 수 있음.
- 음수 사이클이 존재하는 경우엔 적용 불가
구현
import java.util.Arrays;
public class FloydWarshall {
// 무한대를 나타내는 상수
static final int INF = Integer.MAX_VALUE;
// 플로이드-워셜 알고리즘을 실행하는 메서드
public static void floydWarshall(int[][] graph) {
int V = graph.length;
// 최단 거리를 저장할 배열 생성
int[][] dist = new int[V][V];
// 그래프 초기화: 초기 거리를 입력
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
dist[i][j] = graph[i][j];
}
}
// 각 정점 k를 중간 정점으로 사용하여 경로를 최적화
for (int k = 0; k < V; k++) {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
// i에서 j로 가는 경로가 k를 거쳐 더 짧으면 업데이트
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
// 단계별로 배열 상태 출력
System.out.println("경유 정점 " + k + "을(를) 거친 후 거리 배열:");
printSolution(dist);
}
// 최종 결과 출력
printSolution(dist);
}
// 최단 경로 배열을 출력하는 메서드
public static void printSolution(int[][] dist) {
int V = dist.length;
System.out.println("정점 쌍 간의 최단 거리:");
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (dist[i][j] == INF)
System.out.print("INF ");
else
System.out.print(dist[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
// 그래프의 인접 행렬 표현 (0은 자기 자신으로 가는 경로)
int[][] graph = {
{ 0, 5, INF, 10 },
{ INF, 0, 3, INF },
{ INF, INF, 0, 1 },
{ INF, INF, INF, 0 }
};
// 플로이드-워셜 알고리즘 실행
floydWarshall(graph);
}
}