플로이드 워셜 알고리즘

플로이드 워셜(Floyd Warshall) 알고리즘은 동적 계획법으로 모든 최단 경로를 구하는 알고리즘이다.

먼저 초기화를 해줘야 하는데 최단경로가 있으면 최단경로를 없으면 최댓값을 넣어주어야 한다.

그래야 최단경로를 구할 수 있다.

3중 for 문으로 동작하는데 첫 for 문부터 각각 거쳐 가는 점, 출발하는 점, 도착하는 점을 나타낸다.

아래 코드는 초기화를 했다는 가정하에 작성했다.

class Floyd{

     int len = 10;

     int[][] arr = new int[len][len];

     void floyd(){

          for(int i = 0; i < len; i++){ // 거쳐가는 점

               for(int j = 0; j < len; j++){ // 출발하는 점

                    if(i == j){

                         continue;

                    }

                    for(int k = 0; k < len; k++){ // 도착하는 점

                         if(i == k){

                              continue;

                         }

                         if(j != k){

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

                                   arr[j][k] = arr[j][i] + arr[i][k];

                              }

                         }

                    }

               }

          }

     }

}

두 가지의 경우 그냥 지나가면 된다.

     1. j와 k가 같을 때 : 자기 자신을 가리킬 때

     2. i가 j나 k와 같을 때 : 거치는 점이 출발하는 점이나 도착하는 점과 같을 때

코드를 보면 j에서 k로 갈 때 바로 가는 것보다 i를 거쳐서 가는 게 더 빠를 경우 j에서 k로 가는 최단경로를 수정하게 된다.