[알고리즘] 플로이드와샬/FloydWarshall (Graph)

Floyd-Warshall(플로이드와샬 알고리즘)이란?

 - 그래프에서 모든 정점 사이의 최단거리를 구하는 알고리즘.
 - 음수 가중치에 대한 처리가 어려운 다익스트라 알고리즘에 비해 플로이드 와샬 알고리즘은 사이클이 없는 경우 음수 가중치 처리가 가능

 - for문(반복문)을 vertex(정점)만큼 3번 돌기 때문에 O(n3)의 시간 복잡도를 가진다.

 

Floyd-Warshall process

- 2차원 배열의 크기만큼 배열을 선언해준다. (각 정점에서 모든 정점을 가는 최소거리를 표현해줄 것이다.)

- 연결돼있는 부분을 표기해준다.

 

2차원 배열 초기화

- 시작 정점에서 목표 정점까지 바로 가는 거리보다 또 다른 정점을 거쳐 지나가는 거리가 짧으면 업데이트를 해준다.

- 플로이드 워샬 알고리즘에서는 1부터 시작해서 n까지 순차적으로 거쳐지나 가는 정점을 설정해준다.

- ex) 3에서 4로 가는 5의 거리보다 3 -> 2-> 4까지 가는 거리가 짧으므로 업데이트가 될 것이다.

- 이때 3은 시작 정점, 2가 거쳐가는 정점, 4는 목표정점이다.

거쳐지나가는 노드를 1로 설정했을 때 업데이트 될 부분을 색칠함

거쳐지나가는 노드를 2로 설정했을 때 업데이트 될 부분과 업데이트 된 표

- 이런 과정들을 걸쳐 거쳐지나 가는 노드들이 1에서 4까지 반복문을 돌았을 때 2차원 배열에는 각 정점별 최단거리가 기록되어 있을 것이다.

[코드]

public static void main(String[] args) {
        int n = 4;                                //정점 수
        int[][] FW = new int[n+1][n+1];            //인덱스를 편하게 다루기 위해서
        for(int i = 1; i <= n; i++) {            //처음엔 전부 INF만들기
            for(int j = 1; j <= n; j++) {
                FW[i][j] = 1000;                //연결이 안되있는 부분은 어떤 가중치보다 크게 선언
            }
        }
        
        FW[1][4] = 8;            //연결되있는 값 가중치 넣어주기
        FW[1][2] = 4;
        FW[2][4] = 2;
        FW[3][2] = 1;
        FW[3][4] = 5;
        FW[4][3] = 6;
        
        for(int k =1; k<= n; k++) {        //거쳐가는 정점
            for(int i = 1; i<=n; i++) {    //시작 정점
                for(int j = 1; j<=n; j++) {    //도착 정점
                    if(FW[i][j] > FW[i][k]+ FW[k][j]) {
                        FW[i][j] = FW[i][k] + FW[k][j];
                    }
                }
            }
        }
}

 

[플로이드와샬 알고리즘으로 구한 각 정점마다 최단거리 배열]

-코드와 배열은 위에 설명했던 설명대로 구현했다.

나동빈님의 유투브를 보고 공부했다. 부족한 부분이 있다면 아래 링크에서 더 자세한 설명을 듣는걸 추천한다.

https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221234427842&proxyReferer=https:%2F%2Fwww.google.com%2F