음수 사이클이 없는 그래프 내의
모든 정점에서 모든 정점까지의 최단거리를 모두 구할 수 있는 알고리즘.
*음수 사이클 : 사이클의 모든 경로를 지나 원래 지점으로 돌아왔을 때 최종 비용이 음수인 사이클
다이나믹 프로그래밍 기법을 사용한 알고리즘.
인접 행렬을 이용해서 각 노드간 최소 비용을 계산한다.
한 정점에서 한 정점까지 가는 경로의 간선 개수를 0개에서 N개까지 모두 고려.
0개의 간선을 거쳐 가는 경우는 자기 자신밖에 없기 때문에
초기 그래프의 모양은 (r, c) (r==c)을 제외하고 모드 매우 큰 값으로 초기화해준다.
연결되지 않는 경로는 매우 큰 값으로 초기화되어 있을 것이다.
코드
// 플로이드 초기 거리 테이블 초기화
dist = new int[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// 자기 자신으로 가는 길은 최소 비용이 0이다.
if (i == j) {
dist[i][j] = 0;
continue;
}
// 자기 자신으로 가는 경우를 제외하고는 매우 큰 값(N개의 노드를 모두 거쳐서 가더라도 더 큰 값).
dist[i][j] = 100_000_000;
}
}
// 플로이드 워셜 알고리즘
// 노드를 1개부터 N개까지 거쳐가는 경우를 모두 고려한다.
for (int k = 0; k < N; k++) {
// 노드 i에서 j로 가는 경우.
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// k번째 노드를 거쳐가는 비용이 기존 비용보다 더 작은 경우 갱신
// 또는 연결이 안되어있던 경우(INF) 연결 비용 갱신.
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
시간복잡도
모든 노드 V에 대해서 V x V 행렬을 갱신해주므로 O(V^3)의 복잡도를 가진다.
입력 크기에 주의하자
'알고리즘 > 그래프' 카테고리의 다른 글
[Java] 다익스트라 알고리즘 (0) | 2024.09.06 |
---|