[알고리즘] 플로이드 알고리즘

플로이드 알고리즘

 플로이드 알고리즘은 시간복잡도 조건에 여유가 있는경우(O^3) 사용할 수 있는 알고리즘으로, 한 시작점에서 다른 정점까지의 최단 거리를 구하는 다익스트라 알고리즘과 다르게 모든 정점 쌍에 대해서 둘 사이의 최단 거리를 구하는 알고리즘이다.

 

위 가중치 그래프에서, A에서 E로 가기 위한 방법은 (1) A에서 E로 직접 가는 방법과, (2) 중간에 C를 거져가는 방법 총 2가지 방법이 존재한다. 따라서 두 정점 쌍의 최단 거리를 구하기 위해서는 두 정점 사이에 존재하는 경유점을 거쳐가는 방법들을 탐색하며 그 방법들 중에 최소값을 구하면 된다.

 

len[A][E] = Min(len[A][E], len[A][C] + len[C][E])

 

N개의 노드에 대한 플로이드 알고리즘은 O(N^3)의 시간복잡도를 가지므로 N이 크면 사용할 수 없다. 다시 말해 N이 크면 사용할 수 없으므로 인접리스트 대신 NxN 크기의 인접행렬을 사용해도 된다. (구현이 간단하잖아)

 

(인접 행렬을 사용한 다익스트라 알고리즘을 N회 반복하는 것과 시간복잡도가 동일하다. 하지만 다익스트라는 가장 적은 비용을 가지는 노드를 하나씩 꺼낸 다음, 그 노드를 거쳐가는 비용을 갱신하는 로직이라면 플로이드는 모든 노드들을 한 번씩 순서 상관없이 거쳐가는 정점으로 선택하고 최단 거리를 구하도록 구성되어있다.)

 

https://eckrin.tistory.com/125

[알고리즘] Dijkstra

 

기본적으로 노드간의 거리를 사용하는 2차원 배열 dist를 초기화하고, 위에서 언급한 공식을 적용해주면 된다.

 

int[][] dist = new int[N][N];
final int INF = 0x3f3f3f3f;

//initialize
for(int i=0; i<N; i++) {
  for(int j=0; j<N; j++) {
    dist[i][j] = i와j가 연결 ? i와 j의 거리 : INF;
  }
}

//floyd
for(int k=0; k<N; k++) {
  for(int i=0; i<N; i++) {
    for(int j=0; j<N; j++) {
      dist[i][j] = Math.min(dist[i][j], dist[i][k]+dist[k][j]);
    }
  }
}

 

주의할 점

주의점 1. 자기 자신과의 거리는 0으로, 연결되지 않은경우 INF로, 연결된 경우 연결된 거리로 dist를 초기화해주어야 한다.
주의점 2. 이때 3중 for문에서 중간 경유점을 지정하는 for문을 맨 바깥쪽으로 빼주어야 한다. (밑에서 후술)

 

 

 

BOJ 1389) 케빈 베이컨의 6단계 법칙

1. 인접 행렬 초기화할때 직접 연결 간선이 없는 경우 MAX값으로(나는 0x3f3f3f3f), arr[i][j]에서 i==j일경우 0으로 초기화하고 시작했다.

2. 플로이드 알고리즘은 삼중 루프를 갖게 되는데, 이때 경유점을 검사하는 루프를 가장 바깥에 두어야 한다. (안쪽에서 경유점을 검사할 경우, 노드를 반복 검사하지 않아 오류가 발생하는 것 같다.) 또한 경유점 k의 순서는 중요하지 않다.

 

package Main.src;
import java.io.*;

public class BOJ1107 {
    static int N;
    static int M;
    static int[][] KBN;
    static int min = 0x3f3f3f3f;
    static int[] KBNsum;
    static int minIdx;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line_1 = br.readLine().split(" ");
        N = Integer.parseInt(line_1[0]);
        M = Integer.parseInt(line_1[1]);

        KBN = new int[N+1][N+1];
        KBNsum = new int[N+1];

        for(int i=0; i<=N; i++) {
            for(int j=0; j<=N; j++) {
                if(i!=j)
                    KBN[i][j] = 0x3f3f3f3f;
                else
                    KBN[i][j] = 0;
            }
        }

        for(int i=0; i<M; i++) {
            String[] line_N = br.readLine().split(" ");
            KBN[Integer.parseInt(line_N[0])][Integer.parseInt(line_N[1])] = 1;
            KBN[Integer.parseInt(line_N[1])][Integer.parseInt(line_N[0])] = 1;
        }

        floyd();
        printrst();
    }

    public static void printrst() {
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                KBNsum[i] += KBN[i][j];
            }
        }

        for(int i=1; i<=N; i++) {
            if(min>KBNsum[i]) {
                min = KBNsum[i];
                minIdx = i;
            }
        }
        System.out.println(minIdx);
    }

    public static void floyd() { 
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                for(int k=1; k<=N; k++) {
                    KBN[j][k] = Math.min(KBN[j][k], KBN[j][i]+KBN[i][k]);
                    KBN[k][j] = KBN[j][k];
                }
            }
        }
    }
}