모든 쌍의 최단거리는 플로이드

문제를 풀다 보면, 한 정점에서 시작 해서 다른 정점으로 가는 최단거리가 아니라, 모든 가능한 정점 쌍의 최단거리를 알 필요가 있을 때도 있습니다. 그럴땐 모든 정점에 대해서 다익스트라 알고리즘이나, 벨만-포드 알고리즘을 사용할 수도 있지만, 그 작업을 전문적으로 해내는 플로이드 알고리즘의 구현이 정말 간단하기 때문에, 플로이드 알고리즘도 언급을 하고 넘어가고 싶스빈다. 그리고, 플로이드 알고리즘이 최단경로를 찾는 방식 덕분에, 그래프 관련 문제를 풀 때, 다른 방면에도 응용이 가능하기 때문에 플로이드 알고리즘 또한 제대로 짚고 넘어가도록 합시다.

기본 아이디어

플로이드 알고리즘은 이때까지 소개한 알고리즘과는 또 다른 접근법을 사용해서 최단거리를 찾아냅니다. 플로이드 알고리즘은 경유점 이라는 개념을 사용해서 최단경로를 찾아냅니다.

두 정점 u,v를 잇는 어떤 경로에 대해서 생각해 봅시다. 당연하게도 이 경로는 u,v를 지납니다. 이 외에도 다른 정점을 방문하고 올 수도 있지요. 다른 방문하는 정점들을 경유점이라고 합니다. 일상생활에서 목적지로 가기 위해서 중간에 경유하는 경유지와 비슷한 개념이지요.

정점집합 $S$에 속한 정점들만으로 u에서 v로 가는 최단경로를 $D_S(u,v)$라고 표기합시다.

$D_S(u,v)$에 대해서 조금 더 생각해 봅시다. $S$에서 임의의 정점 하나를 골라서 $x$라는 이름을 붙여 봅시다. $x$가 임의의 정점이기 떄문에 $D_S(u,v)$는 두가지 경우가 있을 수 있겠습니다.

1. 경로가 $x$를 경유하지 않는다 : 이 경로는 $S-{x}$에 포함된 정점들만을 경유점으로 사용하겠습니다.
2. 경로가 $x$를 경유한다 : 이 경로를 u에서 $x$까지 가는 구간과, $x$에서 v로 가는 경로로 쪼개 봅시다. 그러면 두 경로들은 당연하게, $S-{x}$에 속한 정점들만을 경유점으로 사용합니다.

$S$를 경유점으로 사용해 u에서 v로 가는 최단경로는 위 두가지 중 짧은 경로가 되므로, 이를 간단히 나타내면 아래와 같습니다.

위의 식에서 $x$는 임의의 정점이기 때문에, 뭐가 되든지 상관 없습니다. 위 과정을 동적 계획법으로 나타내기 쉽게 하기 위해서, $S_k=\{0,1,2,...,k\}$라고 하고, $C_k = D_{S_k}$라고 합시다. 그러면 위의 식을 아래와 같이 고쳐쓸 수 있습니다.

알고리즘의 프로토타입과 최적화

위의 설명을 그대로 코드로 옮겨 봅시다. 위의 점화식에서 $C_k$의 모든 값은 $C_{k-1}$에만 의존하므로, 반복적 동적 계획법을 이용하여 쉽게 코드를 작성할 수 있습니다.

int V;
int adj[MAX_V][MAX_V];
int C[MAX_V][MAX_V][MAX_V];
void allPairShortest(){
    for(int i = 0; i < V; ++i)//C[0]을 초기화
        for(int j = 0; j < V; ++j)
            if(i != j)
                C[0][i][j] = min(adj[i][j], adj[i][0] + adj[0][j]));
            else C[0][i][j] = 0;
    for(int k = 1; k < V;++k)
        for(int i = 0; i < V; ++i)
            for(int j = 0;j < V; ++j)
                C[k][i][j] = min(C[k-1][i][j], C[k-1][i][k] + C[k-1][k][j]);
 }

위 코드의 시간 복잡도는, 삼중 반복문에 의해서 좌우되므로, $O(|V|^3)$ 이라는 것을 간단하게 알 수 있습니다. 하지만 위 코드에는 치명적인 문제가 있는데, C[][][]가 너무나 많은 메모리를 잡아먹고 있다는 것입니다. 사실 $C_k$의 답은, $C_{k-1}$만 있으면 계산할 수 있기 떄문에, 모든 k에 대해서 C 값들을 저장할 필요는 없습니다. 그리머므로 슬라이딩 윈도우 기법을 이용해서 값을 C[k%2][u][v]에 저장할 수도 있겠지만, 이것보다 더 줄여 버릴수 있습니다.

점화식을 한번 더 주의깊게 살펴 봅시다. $C_k(u,v)$를 계산하기 위해서, 필요한 값은 $C_{k-1}(u,k)$와 $C_{k-1}(k,v)$ 뿐입니다. $C_{k-1}(u,v)$는 예전에 있던 값으로 단순 비교 대상일 뿐입니다. 만약에, $C_k(u,k)$와 $C_{k-1}(u,k)$, 그리고 $C_k(k,v)$와 $C_{k-1}(k,v)$가 서로 같은 값이라면, 이 둘을 구분하지 않고 2차원 배열 하나로 퉁쳐버려도 상관 없게 됩니다. 관연 그 두 쌍이 각각 같은 값을 가지는지 생각해 봅시다.

위에서 언급한 이야기를 잠깐 꺼내오겠습니다.

2. 경로가 $x$를 경유한다 : 이 경로를 u에서 $x$까지 가는 구간과, $x$에서 v로 가는 경로로 쪼개 봅시다. 그러면 두 경로들은 당연하게, $S-{x}$에 속한 정점들만을 경유점으로 사용합니다.

$C_{k-1}(u,k)$와 $C_{k-1}(k,v)$는 시작점과 끝점에 각각 $k$를 가지고 있으므로, 최단경로를 구함에 있어서, 시작점이나 끝점이 되는 $k$를 경유점으로 삼지 않아도 됩니다. 즉 이는 위에서 언급한 대로, C 배열을 굳이 3차원 배열이 아닌, 2차원 배열로 계산해도 무방하다는 것을 의미하며, 코드가 더 최적화 될 수 있음을 의미합니다.

실제 구현

실제로 이 알고리즘을 구현할 때는, 별도의 배열 C를 만들지 않고, 결과를 인접 행렬 adj[][]에 바로 저장하는 방식또한 사용합니다. 그러면, 굳이 C를 초기화 하지 않아도 되고, 메모리도 더 아낄 수 있는 일거양득의 효과를 누릴 수 있기 때문이죠

int V;
int adj[MAX_V][MAX_V];

void floyd(){
    for(int i = 0; i < V; ++i) adj[i][i] = 0;
    for(int k = 0; k < V; ++k)
        for(int i = 0; i < V; ++i)
            for(int j = 0; j < V;++j)
                adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
}

위 코드에서 모든 i에 대해서 adj[i][i]=0으로 만들었는데, 이는 자기 자신에게로 가는 길이를 0으로 만들어서, 알고리즘이 올바르게 돌아가도록 하기 위해서 입니다.

음수 사이클 판별

플로이드 알고리즘은 음수 사이클 판별도 사실 할 수 있습니다. 방법은 매우 간단합니다.
adj[i][i]를 체크해서, 그 값이 음수라면 0인 것이죠. i에서 출발해서 i로 도착하는 경로의 길이를 처음에 0이라고 하였는데, 이게 개선되어서 0보다 작아졌다면, i에서 i로 가는 경로, 즉 사이클의 가중치가 음수가 되었다는 뜻이니까요.

실제 경로 찾기

플로이드 알고리즘은 이때까지의 경로 탐색 알고리즘과 작동방법이 많이 다르기 때문에, 부모의 정보를 저장하는 방식으로 실제 경로 복원이 이루어지지 않습니다. 대신, 경유점을 이용해서 최단 경로를 찾는 알고리즘 답게, 경유점을 저장해서, 그 정보를 바탕으로 실제 경로를 복원해 냅니다. 직접 코드를 봅시다.

int V;
int adj[MAX_V][MAX_V];
int via[MAX_V][MAX_V];//경유점을 저장하는 배열. -1로 초기화해 둔다

void floyd(){
    for(int i = 0; i < V; ++i) adj[i][i] = 0;
    for(int k = 0; k < V; ++k)
        for(int i = 0; i < V; ++i)
            for(int j = 0; j < V;++j){
                adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
                via[i][j] = k;
            }
}

void reconstruct(int u, int v, vector<int>& path){//u에서 v로 가는 경로를 path에 저장
    if(via[u][v] == -1){
        path.push_back(u);
        if(u != v) path.push_back(v);
    }
    else{
        int w = via[u][v];
        reconstruct(u,w,path);
        path.pop_back();//w가 중복되어서 들어가므로 지운다
        reconstruct(w,v,path);
    }
}

플로이드 알고리즘의 변형

다른 최단거리 알고리즘과 다르게, 플로이드 알고리즘은 여러 문제 상황에서 문제에 맞는 알고리즘으로 변형해서 쓸 수 있는 특징을 가지고 있습니다.

다른 알고리즘들은 간선을 이용해서 최단경로를 평가하지만, 플로이드 알고리즘은 경유점 이라는 정점을 기준으로 해서 최단경로를 평가합니다. 만약에, 정점을 자나는 데에도 비용이 든다고 하면, 다른 알고리즘으로는 정점 하나를 분리해서, 정점 내부를 다니는 간선을 만들어서 탐색을 해야겠지만, 플로이드 알고리즘의 경우에는, 최단거리를 갱신하는 부분만 살짝 바꿔 주면 그런 문제를 별도의 관정을 거치지 않고 해결할 수 있습니다.

또, 점차적으로 간선이 추가 되는 그래프에 대응하기에 용이합니다. 원본 플로이드 알고리즘은, 경유할 수 있는 정점을 기준으로 탐색을 해나갔지만, 간선을 기준으로 탐색을 하면, 집합에 추가되는 순서를 고려하면서 시간을 아끼면서 간선이 추가되는 상황에서의 최단경로를 구해낼 수 있습니다.