[알고리즘] 플로이드 알고리즘(Floyd Algorithm)

플로이드 알고리즘

플로이드 알고리즘은 최단 경로를 구하는 유명한 알고리즘이다. 다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘인 반면, 플로이드 알고리즘은 모든 노드 간의 최단 경로를 구하는 방법이다. 2차원 인접 행렬을 구성해서 경로마다 더 짧은 길이를 선택해 줄이는 과정을 반복한다. 플로이드와 다익스트라에 대한 자세한 내용은 [자료구조] Graph(그래프) - 최단 경로 알고리즘을 참고하면 된다.

플로이드 알고리즘은 모든 경로를 확인해야 하기 때문에 Brute Force 방법으로 접근할 수 있다. 그러나, 시간복잡도가 O(n!)이므로 효율적인 다른 방법을 사용해야 한다. Dynamic Programming을 사용하면, n!인 시간복잡도를 조금 더 줄일 수 있다.

 

 

Dynamic Programming

가중치가 있는 방향 그래프일 때, 위와 같은 인접 행렬 관계식을 만들 수 있다. 그래프에서 최단 경로의 길이를 저장하는 배열 D를 생성해 사용할 것이다.

예를 들어, 배열 D[1][2]을 구하고자 한다. 그러면 노드 1에서 노드 2로 바로 가는 경로가 짧은지, 노드 1에서 다른 노드 k를 들러서 노드 3으로 가는게 짧은지 비교해야 한다. 이를 바탕으로 점화식을 만들어 보면, D[i][j] = min(D[i][j], D[i][k] + D[k][j])이다.

 

// 최단경로 길이
#define INF 0xffff

typedef vector<vector<int>> matrix_t;

void floyd(int n, matrix_t& W, matrix_t& D) {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            D[i][j] = W[i][j];
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                D[i][j] = min(D[i][j], D[i][k] + D[k][j]); // 최단경로
}

 

먼저 배열 D를 인접 행렬 W로 초기화하고, i부터 j까지 거리와 i부터 k + k부터 j까지 거리를 비교해 저장한다. 이때, 시간복잡도는 O(n^3) 이다.

이것보다 더 효율적으로 만들 수 있을까?

 

1차원 배열을 사용하면 가능하다. k번째 반복을 하는 중에는 k번째 행과 열이 그대로이기 때문이다.

// 코드

---

 

위는 최단 경로의 길이를 구하는 알고리즘이다.그렇다면, 최단 경로를 구하는 방법은 무엇일까?

새로운 배열 P에 최적의 노드를 기록하면 된다. 최단 경로의 길이가 구해지면, 배열 P에 최단 경로의 노드 k 를 저장하면 된다.

// 최단 경로
void floyd2(int n, matrix_t& W, matrix_t& D, matrix_t& P) {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            D[i][j] = W[i][j];
            P[i][j] = 0;
        }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (D[i][j] > D[i][k] + D[k][j]) {
                    D[i][j] = D[i][k] + D[k][j];
                    P[i][j] = k;
            }
}

 

주의해야 할 것은, 모든 경우에서 최단 경로임을 만족해야 Dynamic Programming으로 풀 수 있다.