[알고리즘-자바] Floyd-WarShall 알고리즘

플로이드 와샬

모든 정점에서 모든 정점으로의 최단 거리를 구하기 위해서 플로이드 와샬 알고리즘을 사용할 수 있습니다. 즉, 정점 [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();
        }
    }
}