최적 경로 찾기 #4 - 플로이드 워셜(Floyd Warshall) 알고리즘, 자바 코드 구현 포함

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

플로이드 알고리즘은 로버트 플로이드(Robert W Floyd)이 발표한 알고리즘으로 버나드 로이(Bernard Roy)가 발표한 알고리즘, 스티븐 워셜(Stephen Warshall)이 발표한 알고리즘과 비슷하기 때문에 플로이드 알고리즘, 로이-워셜 알고리즘, 로이-플로이드 알고리즘 이라고도 불린다.

플로이드 알고리즘은 두 노드 사이에 존재하는 노드와의 가중치를 이용해 최소 가중치 합 경로를 구하는 알고리즘이다. 

가능한 모든 경우의 수를 따지므로 시간복잡도가 크지만, 모든 노드에서 자신을 제외한 모든 노드로 가는 최소 가중치 경로를 얻을 수 있다.

플로이드 알고리즘이 다익스트라, 벨만 포드 알고리즘과의 가장 큰 차이점은 어떤 정점에서든지 최단 경로를 바로 탐색 가능하다는 점이다. 플로이드 알고리즘은 동적계획 방식을 활용하는데, 동적 계획이란 거리를 계산하는 중에 이미 계산된 결과가 현재 실행되는 계산에 반영되는 방법으로서 플로이드 알고리즘에서는 현재 선택된 정점을 기준으로 다음 정점을 계산하여 지속적으로 최적화 작업을 수행하여 최단경로를 탐색한다.

 

플로이드 알고리즘의 가장 큰 특징으로는 

자신 노드를 제외한 모든 노드로 가는 경로의 최소 가중치를 얻는다는 점이다. 목표 노드로의 최소 가중치 값을 이용해 어떤 노드로 이동하는 것이 가장 효율적인지 판단할 수 있다. 

또한 자기 자신으로 가는 가중치는 0으로 설정하고, 연결되지 않은 노드의 가중치는 무한(infitiny)을 설정한다는 점이다.

자기 자신을 제외한 인접 노드들과의 가중치 비교를 해야하기 때문에 연결되지 않은 노드는 가중치 비교가 무시되도록 무한으로 설정한다.

 

플로이드 알고리즘 수도코드

기본개념

1. 대부분의 플로이드 알고리즘은 인접 행렬을 이용하기 때문에 경로를 탐색하려는 데이터를 인접 행렬로 변환한다.

2. 정점과 정점 사이의 거리 값을 정점 사이의 또 다른 정점을 거칠 경우의 거리 값과 비교한다. 

2. 비교 후 더 작은 거리 값을 지속적으로 계산에 반영한다. 

3. 반복 후 최종적으로 남은 값이 각 정점들 간의 최단거리 값으로 정해진다.

 

해당 그래프를 기준으로 자바 코드로 구현해본 예제는 다음과 같다.

코드구현

public class SampleCode {
    private final int INF = 9999;
    
    public void floyd(int matrix[][]){
        int num = matrix.length;

        //연결되지 않는 노드 무한값 설정
        for (int i = 0; i < num; i++){
            for (int j = 0; j < num; j++) {
                if(i != j){
                    if(matrix[i][j] == 0){
                        matrix[i][j] = INF;
                    }
                }
            }
        }
        

        int s, m, e;
        for (m = 0; m < num; m++) { //가운데 노드
            for (s = 0; s < num; s++) { //시작 노드
                for (e = 0; e < num; e++) { // 마지막 노드
                    if (matrix[s][e] > matrix[s][m] + matrix[m][e])
                        matrix[s][e] = matrix[s][m] + matrix[m][e]; //가운데를 거쳐가는 것이 더 빠르면 그 경로로 업데이트
                }
            }
        }
        printMatrix(matrix);
    }

    void printMatrix(int matrix[][]) {
        int num = matrix.length;

        for (int i = 0; i < num; ++i) {
            for (int j = 0; j < num; ++j) {
                if (matrix[i][j] == INF)
                    System.out.print("INF ");
                else
                    System.out.print(matrix[i][j] + "  ");
            }
            System.out.println();
        }
    }
    
    
    public static void main(String[] args) {
        SampleCode sample = new SampleCode();
//                         A, B, C, D, E, F, G, H, I, J, K, L
        int graph[][] =  {{0, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0} //A
                        , {2, 0, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0} //B
                        , {3, 4, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0} //C
                        , {0, 4, 2, 0, 9, 0, 3, 1, 0, 0, 0, 0} //D
                        , {0, 0, 0, 9, 0, 1, 0, 0, 2, 3, 0, 0} //E
                        , {0, 0, 0, 0, 1, 0, 0, 2, 0, 0, 5, 4} //F
                        , {0, 0, 1, 3, 0, 0, 0, 0, 0, 0, 7, 0} //G
                        , {0, 0, 0, 1, 0, 2, 0, 0, 0, 0, 0, 0} //H
                        , {0, 0, 0, 0, 2, 0, 0, 0, 0, 5, 0, 2} //I
                        , {0, 0, 0, 0, 3, 0, 0, 0, 5, 0, 0, 0} //J
                        , {0, 0, 0, 0, 0, 5, 7, 0, 0, 0, 0, 3} //K
                        , {0, 0, 0, 0, 0, 4, 0, 0, 2, 0, 3, 0}}; //L

        sample.floyd(graph);
    }
}

 

 

 

Reference.

강창욱, 이형옥. (2022). 현대 교통 상황에서 플로이드 알고리즘의 활용. 한국컴퓨터교육학회 학술발표대회논문집, 26(1), 145-148.

문종헌, 유원선, 차주환. (2016). 최적 경로 알고리즘들의 계산비용 비교 및 트랜스포터의 최적 블록 운송 계획 적용. 대한조선학회 논문집, 53(2), 115-126.

이관우, 강민성, 장진우. (2020). SEIR 모델을 이용한 교통수단에서의 전염병 확산 모델 설계 및 안전경로 추천 알고리즘 구축. 한국정보통신학회 종합학술대회 논문집, 24(2), 54-57.

https://www.programiz.com/dsa/floyd-warshall-algorithm