[Algorithm] 플로이드 와샬(Floyd Warshall) 알고리즘

플로이드 와샬이란

모든 최단 경로를 구하는 알고리즘이다. 

다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이라고 한다면, 플로이드-와샬은 한번 실행하여 모든 노드간 최단 경로를 구할 수 있는 것이다.

 

다익스트라 알고리즘이 가장 적은 비용을 하나씩 선택했다면 플로이드 와샬 알고리즘은 기본적으로 거쳐가는 정점을 기준으로 알고리즘을 수행한다는 점에서 그 특징이 있다.

 

플로이드 와샬 알고리즘의 과정

예시로 모든 노드간의 최단거리를 구해야하므로 2차원 인접 행렬을 구성한다.

알고리즘은 여러 라운드로 구성됩니다. 라운드마다 각 경로에서 새로운 중간 노드로 사용할 수 있는 노드를 선택하고, 더 짧은 길이를 선택하여 줄이는 과정을 반복한다.

 

초기 그래프를 인접행렬로 나타내면 다음과 같습니다. INF는 해당 노드에서 특정 노드까지 가는 길이 없다는 뜻입니다.

0	5	INF	9	1
5	0	2	INF	INF
INF	2	0	7	INF
9	INF	7	0	2
1	INF	INF	2	0

 

• ROUND 1 : 1번 노드를 새로운 중간 노드로 설정

이 그래프는 1번부터 5번 노드까지 존재하므로 알고리즘은 총 5라운드의 과정을 거칩니다. 즉, 모든 노드들을 중간 노드로 선정하는 과정을 각 라운드마다 거칩니다. 예를 들어 2라운드는 2번 노드가 중간 노드이며, 3라운드는 3번 노드가 중간 노드가 될 것입니다.

2번에서 4번으로 가는 길은 원래 없었으나, 1번 노드를 중간 노드로 선정할 경우 2-1-4(길이 5+9=14) 로 갈 수 있게 됩니다. (업데이트된 길이는 📍로 표시)

0	5	INF	9	1
5	0	2	14📍	6📍
INF	2	0	7	INF
9	14📍	7	0	2
1	6📍	INF	2	0

• ROUND 2 : 2번 노드를 새로운 중간 노드로 설정

1번-3번 노드를 잇는 경로, 3번-5번 노드를 잇는 경로가 새로 생기게 됩니다.

0	5	7📍	9	1
5	0	2	14	6
7📍	2	0	7	8📍
9	14	7	0	2
1	6	8📍	2	0

 

이런 과정으로 5번 노드를 중간 노드로 선정하는 라운드까지 모두 거치면 행렬에는 모든 노드 간 최단 거리가 들어가게 됩니다.

소스코드로 구현

플로이드-워셜 알고리즘은 시간 복잡도가 O(n^3)으로, 그래프의 크기가 작아 세제곱 시간 알고리즘을 적용해도 문제가 풀릴 때만 사용할 수 있습니다.

• 먼저, adj에 저장된 인접 행렬의 값을 활용하여 최단 거리 배열인 dist 배열을 초기화합니다.

for(int i = 1; i<=n; i++){
    for(int j =1; j<=n; j++){
        if (i == j) dist[i][j] = 0;
        else if (adj[i][j]) dist[i][j] = adj[i][j];
        else dist[i][j] = INF;
    }
}

 

• 이후, 각 라운드별로 중간 노드가 될 노드 번호를 for문 가장 바깥의 k로 삼습니다. 내부 이중 for문에는 i, j를 통해 각 노드별 모든 거리를 살펴보면서 k를 중간 노드로 삼을 때와 아닐 때의 값을 비교해 더 작은 값으로 업데이트합니다.

for(int k = 1; k<= n; k++){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j<=n; j++){
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
        }
    }
}

 

전체 코드

public class FloydWarshall {
    // 무한대를 나타내는 값
    static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {
        int[][] graph = {
                {0, 5, INF, 8},
                {INF, 0, 3, INF},
                {INF, INF, 0, 1},
                {INF, INF, INF, 0}
        };

        floydWarshall(graph);
    }

    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];
            }
        }

        // 플로이드-와샬 알고리즘 수행
        for (int k = 0; k < V; k++) {
            for (int i = 0; i < V; i++) {
                for (int j = 0; j < V; j++) {
                    if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }

        // 결과 출력
        printSolution(dist, V);
    }

    static void printSolution(int[][] dist, int V) {
        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();
        }
    }
}

 

참고

https://chanhuiseok.github.io/posts/algo-50/

알고리즘 - 플로이드-워셜(Floyd-Warshall) 알고리즘

https://blog.naver.com/ndb796/221234427842

24. 플로이드 와샬(Floyd Warshall) 알고리즘

https://propercoding.tistory.com/109

[알고리즘] 플로이드 와샬 (Floyd Warshall)

https://ssungkang.tistory.com/entry/Algorithm-%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%99%80%EC%83%ACFloyd-Warshall-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[Algorithm] 플로이드 와샬(Floyd-Warshall) 알고리즘