-
[알고리즘-자바] Floyd-WarShall 알고리즘CS/알고리즘(algorithm) 2024. 3. 9. 13:15
플로이드 와샬
모든 정점에서 모든 정점으로의 최단 거리를 구하기 위해서 플로이드 와샬 알고리즘을 사용할 수 있습니다. 즉, 정점 [A, B, C, D]가 존재할 때 A->C로 이동하기 위해서 중간에 B를 거치거나 D를 거쳐 갈 수 있습니다. B와 D를 거치는 게 A->C로 가는 것보다 더 짧은 거리로 이동할 수도 있고 아닐 수도 있습니다. 또한 기존에는 지나갈 수 없는 경로를 다른 정점을 거쳐 지나갈 수 있는 경로가 되기도 합니다.
다음 방향 그래프가 존재합니다.
무한대의 의미는 해당 방향으로 이동하는 경로가 존재하지 않음을 의미합니다 => ex. 정점A -> 정점C
정점A 정점B 정점C 정점D 정점A 0 4 무한대 6 정점B 3 0 7 무한대 정점C 5 무한대 0 4 정점D 무한대 무한대 2 0 위의 정보를 이용하여 모든 정점에 대해서 모든 정점으로 이동하는 최단 거리를 구해보겠습니다.
정점A를 거쳐가기
먼저, 정점A를 거쳐갔을 때 더 짧은 거리로 이동할 수 있는지 확인하겠습니다.
거쳐갈 정점으로 A를 선택했다면 출발 정점이 A인 경우를 고려하지 않아도 됩니다. 왜냐하면 출발 정점이 A라면 반드시 A를 거쳐간다는 의미가 되기 때문입니다 => ex. A->B 이동 시에 반드시 A를 거쳐간다.
출발 정점B
따라서 출발 정점으로 B를 선택하여 최단 거리를 구해보겠습니다.
- B->A : 종점으로 A로 이동한다. 이 또한 중간 노드로 A를 거쳐갈 필요가 없으므로 고려하지 않는다.
- B->B : 출발과 종점이 같은 경우에는 고려하지 않는다.
- B->C : 두 가지 케이스가 존재하며, 더 짧은 이동거리는 7이므로 기존 값을 유지합니다.
- B->C로 이동하는 기존 거리는 7이다.
- B->A->C로 이동하는 거리를 구한다. B->A 이동거리는 3이며 A->C 이동거리는 무한대입니다. 따라서 B->A->C 이동거리는 무한대가 된다.
- B->D : 두 가지 케이스가 존재하며, A로 거쳐가는 이동거리가 더 짧기 때문에 B->D 이동거리를 9로 수정합니다.
- B->D로 이동하는 기존 거리는 무한대이다.
- B->A->D로 이동하는 거리를 구한다. B->A 이동거리는 3이며, A->D로 이동하는 거리는 6이다. 따라서 B->A->D 이동거리는 9가 된다.
정점B의 기존 이동거리
정점 A B C D B 3 0 7 무한대 정점B의 갱신된 이동거리
기존에는 B->D로 이동할 수 없던 경로가, A를 거쳐감으로써 이동할 수 있게 되었습니다.
정점 A B C D B 3 0 7 9 출발 정점C
- C->B: 두 가지 케이스가 존재한다. A를 거쳐가는 경로가 더 짧으므로 이동거리를 수정한다.
- C->B : 무한대
- C->A->B : C->A(5) + A->B(4) = 9
- C->D : 기존 거리가 더 짧으므로 이동거리를 유지한다.
- C->D : 4
- C->A->D : C->A(5) + A->D(6) = 11
기존 거리
정점 A B C D C 5 무한대 0 4 갱신된 거리
정점 A B C D C 5 9 0 4 출발 정점D
- D->B : 기존 이동거리를 유지한다.
- D->B : 무한대
- D->A->B : D->A(무한대) + A->B(4) = 무한대
- D->C : 기존 이동거리를 유지한다.
- D->C : 2
- D->A->C : D->A(무한대) + A->C(무한대) = 무한대
정점D로 시작하는 이동거리는 갱신되지 않는다.
정점 A B C D D 무한대 무한대 2 0 정점A를 거쳐가는 이동거리 최종 테이블
기존 테이블
정점A 정점B 정점C 정점D 정점A 0 4 무한대 6 정점B 3 0 7 무한대 정점C 5 무한대 0 4 정점D 무한대 무한대 2 0 정점A를 중간에 거쳐감으로써 갱신된 이동거리이다.
정점A 정점B 정점C 정점D 정점A 0 4 무한대 6 정점B 3 0 7 9 정점C 5 9 0 4 정점D 무한대 무한대 2 0
정점B를 거쳐가기
아래 테이블을 사용하여 이동거리를 탐색합니다.
정점A 정점B 정점C 정점D 정점A 0 4 무한대 6 정점B 3 0 7 9 정점C 5 9 0 4 정점D 무한대 무한대 2 0 정점B를 거쳐가는 이동거리 최종 테이블
정점A 정점B 정점C 정점D 정점A 0 4 11 6 정점B 3 0 7 9 정점C 5 9 0 4 정점D 무한대 무한대 2 0
정점C를 거쳐가기
아래 테이블을 사용하여 이동거리를 탐색합니다.
정점A 정점B 정점C 정점D 정점A 0 4 11 6 정점B 3 0 7 9 정점C 5 9 0 4 정점D 무한대 무한대 2 0 정점C를 거쳐가는 이동거리 최종 테이블
정점A 정점B 정점C 정점D 정점A 0 4 11 6 정점B 3 0 7 9 정점C 5 9 0 4 정점D 7 11 2 0
정점D를 거쳐가기
아래 테이블을 사용하여 이동거리를 탐색합니다.
정점A 정점B 정점C 정점D 정점A 0 4 11 6 정점B 3 0 7 9 정점C 5 9 0 4 정점D 7 11 2 0 정점D를 거쳐가는 이동거리 최종 테이블
정점A 정점B 정점C 정점D 정점A 0 4 8 6 정점B 3 0 7 9 정점C 5 9 0 4 정점D 7 11 2 0
플로이드 와샬을 사용한 최종 테이블
기존 테이블
정점A 정점B 정점C 정점D 정점A 0 4 무한대 6 정점B 3 0 7 무한대 정점C 5 무한대 0 4 정점D 무한대 무한대 2 0 알고리즘을 적용한 테이블
정점A 정점B 정점C 정점D 정점A 0 4 8 6 정점B 3 0 7 9 정점C 5 9 0 4 정점D 7 11 2 0 플로이드 와샬 알고리즘을 적용하여 모든 정점에 대하여 모든 정점으로 이동하는 거리를 갱신할 수 있었습니다.
플로이드 와샬 자바 코드
public class FloydWarshall { public static void main(String[] args) { int n = 4; // 정점 개수 int[][] graph; // 방향 그래프 // 그래프 초기 값 입력 graph = new int[][]{ {0, 4, 210000000, 6}, {3, 0, 7, 210000000}, {5, 210000000, 0, 4}, {210000000,210000000, 2, 0}, }; /** * k = 정점A -> 정점B 이동 시에 거쳐 갈 정점 * ex. 정점A -> 정점K -> 정점B */ for (int k = 0; k < n; k++) { for (int y = 0; y < n; y++) { for (int x = 0; x < n; x++) { int oldPath = graph[y][x]; int newPath = graph[y][k] + graph[k][x]; graph[y][x] = Math.min(oldPath, newPath); } } } for (int y = 0; y < n; y++) { for (int x = 0; x < n; x++) { System.out.print(graph[y][x] + " "); } System.out.println(); } } }