[그래프] Graph 9: Floyd 플로이드의 모든 쌍 최단 거리 알고리즘

1.플로이드의 모든 쌍 최단 거리 알고리즘

 

모든 정점 쌍에 대해 둘 사이의 최단 거리를 구해야 할 때도 있다.

 

 

이런 문제를 해결하는 가장 간단한 방법은 각 정점을 시작으로

 

다익스트라 알고리즘을 반복해서 실행하는 것이다.

(음수가 있다면 벨만-포드 알고리즘 사용)

 

 

플로이드 알고리즘은 그래프의 모든 정점 쌍의 최단 거리를 저장하는 배열 dist[][]를 계산한다.

(동적 계획법)

 

이 배열의 원소 dist[u][v]는 정점  u에서 v로 가는 최단 거리를 나타낸다.

 

 

2. 정점의 경유점들

 

두 정점 u, v를 잇는 어떤 경로가 있다고 하자

 

이 경로는 u, v를 지나가고 다른 정점 또한 지나갈 수 있다.

 

u와 v를 직접 연결하는 간선이 없거나, 다른 정점을 경유해서 가는 편이 전체 경로가 더 짧아질 수 있기 때문이다.

 

이와 같이 경로가 거쳐가는 정점들을 경유점이라고 한다.

 

 

 

경유점들의 집합을 S

최종적으로 계산하고 싶은 값을 전체 정점 집합 V를 모두 경유점으로 쓸 수 있는 Dv(u, v)

두 정점 사이를 잇는 간선중 가장짧은 간선의 길이 w(u, v)는 D||(u, v) 라고 하자

 

 

 

S에 포함된 정점만을 경유점으로 사용해 u에서 v로 가는 최단 경로를를 알고있다고 하자

S 중에 정점을 하나 골라 x라고 하면, 최단 경로는 x를 경유할 수도 있고, 경유하지 않을 수도 있다.

각 경우에 최단 경로는 어떤 형태를 가지는지 봐보자

 

1. 경로가 x를 경유하지 않는다: 이 경로는 S - {x}에 포함된 정점들만을 경유점으로 사용한다

 

2. 경로가 x를 경유한다: 이 경로를 u에서 x로 가는 구간과 x에서 v로 가는 구간으로 나눌 수 있다.

                                이 두 개의 부분 경로들은 각각 u와 x, x와 v를 잇는 최단 경로들이어야한다.

                                당연하게도 두 개의 부분 경로들은 x를 경유하지 않으며

                                따라서 S -{x}에 포함된 정점들만을 경유점으로 사용한다.

 

 

S를 경유점으로 사용해 u에서 v로 가는 최단 경로는 위 두 가지 중 더 짧은 경로가 된다,

 

따라서 Ds(u, v) 를 다음과 같이 재귀적으로 정의 할 수 있다.

Ds(u, v) = min{ Ds-|x| (u, x) + Ds-|x| (x, v)  ,  Ds-|x| (u, v) }    

, x∈S

 

 

 

3. 플로이드 알고리즘의 프로토타입

clrs

위의 점화식을 고치면 모든 쌍에 대한 최단 거리 문제를 동적 계획법으로 풀 수 있다.

 

Sk = {0, 1, 2, ... , k} 라 하고, Ck = Dsk 라고 하자

 

Ck(u, v) 는 0번 정점부터 k번 정점까지만을 경유점으로 썼을 때  

 

u에서 v까지 가는 최단 경로의 길이가 된다.

 

이때 점화식은 다음과 같다.

 

 

Ck(u, v) = min{ Ck-1 (u, k) + Ck-1(k, v)

                    , Ck-1 (u, v) }

 

 

이 점화식에서 Ck의 모든 값은 Ck-1에만 의존한다

 

따라서 이는 동적 계획법을 이용하면 쉽게 해결할 수 있다.

 

Ck(u, v) => C[k][u][v] 에 저장된다.

 

따라서 함수 종료후 최단거리는 C[V-1][u][v] 이다.

 

 

 

인접 행렬 표현에서 두 정점 사이에 간선이 없는 경우 아주 큰 값을 넣어둔다.

이러면 경로가 존재하지 않는 경우를 따로 처리하지 않아도 된다.

 

C[0][u][u] 는 항상 0으로 초기화 된다, 자기 자신으로 가는 간선이 따로 없더라도

최단 거리는 항상 0이기 때문이다.

 

이 알고리즘의 시간 복잡도는 3중 for문이 지배한다.

각각은 O(|V|)번 수행되기 때문에 전체 시간 복잡도는 O(|V|^3)이 된다.

const int MAX_V = 10;
int V;
int adj[MAX_V][MAX_V];
int C[MAX_V][MAX_V][MAX_V];
void allPairShortestPath1()
{
    for(int i = 0; i < V; i++)
        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]);
        }
    }
}

 

 

4. 메모리 사용 줄이기

 

이 알고리즘은 대부분의 경우 |V|번 다익스트라나 벨만-포드 알고리즘을 수행하는 것 보다 효율적이다.

 

구현도 간단하고, 반복문 내부가 단순하기 때문에 수행 속도도 빠르다

 

하지만 위 알고리즘은 메모리가 많이 필요하다.

 

 

메모리 문제는 슬라이딩 윈도우 기법을 사용하여 배열의 크기를 O(|V|^2) 만큼 줄일 수 있다.

 

바로 이전의 상태만 필요로 하기 때문에 이는 사용할 수 있다.

 

 

플로이드의 최단 거리 알고리즘은 여기에서 또 

 

별도의 배열을 사용하지 않고 그래프의 가중치를 담는 인접 행렬 위에서 곧장 이 점화식을 계산하여 

 

최적화 시킨다.

 

Ck(u, v) 를 계산하기 위해 필요한 값은 Ck-1(u, k) 와 Ck-1(k, v) 뿐임을 알 수 있다.

 

 

Ck-1(u, k) = 시작점부터 k-1번 정점까지를 경유점으로 이용해 u->k로 가는 최단 경로의 길이

Ck(u, k) = 시작점부터 k번 정점까지를 경유점으로 이용해 u에서 k로 가는 최단 경로의 길이

 

 

출발점이나 도착점이 k번 정점일 때 사용 가능한 경유점의 목록에 k가 추가되는 것은 아무런 의미가 없다.

 

따라서 Ck-1 과 Ck를 구분할 필요가 없어진다.

 

const int MAX_V = 10;
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]);
}

 

 

 

5. 플로이드 알고리즘의 최적화

 

두번째 for문 바로 다음에 i에서 k로 가는 경로가 있는지 확인하면 10% 20% 성능이 향상된다.

 

 

 

6. 실제 경로 계산하기

 

플로이드 알고리즘은 최단 경로에 간선을 하나씩 추가해 가는 다익스트라나 벨만-포드 알고리즘과 다른 방식으로 동작하기 때문에, 실제 경로를 계산하는 과정도 아주 다르다

 

 

스패닝 트리에서 부모정점을 기록하는 다른 알고리즘과 달리

 

 

플로이드 알고리즘에서는 갱신했던 마지막 k의 값을 저장해두면된다.

 

이 정점의 번호를 w라고 하자

 

이 정점을 경유하니까 adj[u][v]가 최소치가 되었다는 것이다.

 

u에서 w로 가는 최단 경로를 찾고, w에서 v로 가는 최단 경로를 찾은 뒤

 

이 둘을 합치면 u에서 v에서 가는 최단 경로를 얻을 수 있다.

 

이를 이용하여 추가 O(|V|^2) 의 메모리만을 사용해서 최단 경로를 계산할 수 있다.

 

 

const int MAX_V = 10;
int V;
int adj[MAX_V][MAX_V];
 
int via[MAX_V][MAX_V];
 
void floyd2()
{
    for(int i = 0; i < V; i++) adj[i][i] = 0;
    memset(via, -1, sizeof(via));
    for(int k = 0; k < V; k++)
        for(int i = 0; i < V; i++)
            for(int j = 0; j < V; j++)
                if(adj[i][j] > adj[i][k] + adj[k][j])
                {
                    via[i][j] = k;
                    adj[i][j] = adj[i][k] + adj[k][j];
                }
}
 
void reconstruct(int u, int v, vector<int>& 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();
        reconstruct(w, v, path);
    }
}

 

 

7. 도달 가능성 확인하기

 

가중치 없는 그래프에서 각 정점간의 도달 가능성 여부를 계산할 수 있다.

 

모든 정점 쌍 u,v에 대해 u에서 v로 가는 경로가 있는지 확인하는 것이다.

 

Ck(u, v)의 정의를 0번부터 k번 정점까지를 경유점으로 썼을 때

 

u에서 v로 가는 경로가 있는지 여부를 나타내도록 변경해보자 그러면 다음과 같은 점화식이 성립한다.

 

Ck(u, v) = Ck-1(u, v) || (Ck-1(u, k) && Ck-1(k, v))

 

 

이것은 최소치를 구하는 연산을 or연산으로 바꾸고 덧셈 연산을 and연산으로 바꾸는 차이밖에 없다.

 

이것은 시간복잡도 면에서 모든 정점에서 시작해서 너비 우선 탐색을 하는 방법보다는 나을 것이 없지만

 

간결한 구현 덕분에 자주 쓰인다.

 

 

 

 

 

- 알고리즘 문제해결전략 952p

 

[그래프] DRUNKEN Drunken Driving