플로이드 와샬 알고리즘

플로이드 와샬 알고리즘

👍처음 보면 어려워 보이지만 풀이를 알고나면 생각보다 쉬운 문제이다.
플로이드 와샬 알고리즘은 기본적으로 모든 경로에 대해서 값을 구하는 알고리즘으로 다익스트라 알고리즘과 비슷하다.

코드

public class Floyd {
    static final int INF = 999999999;


    public static void main(String[] args) throws IOException {
       
		//V는 전달 받은 지도의 크기라 생각하면 됩니다.
        int[][] arr = new int[V + 1][V + 1];

		// 모든 경로를 최대값으로 초기화
        for (int i = 1; i <= V; i++) {
            for (int j = 1; j <= V; j++) {
                if (i != j) {
                    arr[i][j] = INF;
                }
            }
        }

		//각 경로에 대하여 최단값을 전달 받는다는 가정
        for (int i = 0; i < E; i++) {
            arr[start][end] = price;
        }

		//플로이드 와샬 알고리즘
        for (int k = 1; k <= V; k++) {
            for (int i = 1; i <= V; i++) {
                for (int j = 1; j <= V; j++) {
                    if (i == j) {
                        continue;
                    }

                    if (arr[i][j] > arr[i][k] + arr[k][j]) {
                        arr[i][j] = arr[i][k] + arr[k][j];
                    }
                }
            }
        }

        
    }
}

풀이

1. 먼저 모든 값에 대하여 최단 값을 초기화 해준다. 이 때 i==j는 놔두고 다른 값은 모두 큰 값으로 초기화 해준다.
2. 이후 전달 받은 값들을 통해 값을 다시 세팅 해준다.
3. 3중 for문을 돌려서 모든 값에 대하여 최단경로를 설정하는데 여기서 중요한 점은 가장 바깥쪽 k는 경유지이며 i -> start , j->end 경로이다.
4. arr[i][j] > arr[i][k] + arr[k][j]가 의미하는 바는
   i에서 j로 가는 경로 보다 k를 거쳐가는 경로인 arr[i][k] + arr[k][j]가 더 작다면 값을 갱신해 주는 것이다.
   5.위 과정이 끝나고 나면 지도에는 각 지점에 대하여 최소값들이 저장 되게 된다.