플로이드의 모든 쌍 최단 거리 알고리즘
다익스트라 알고리즘과 벨만-포드 알고리즘은 시작점을 기준으로 다른 정점들까지의 최단 경로를 구하는 알고리즘입니다.
하지만 문제에 따라서는 한 개의 시작점이 아닌 모든 정점 쌍에 대해서 둘 사이의 최단 거리를 구해야 할 때도 있습니다.
이런 문제를 다익스트라나 벨만-포드 알고리즘을 이용해서 그래프의 존재하는 모든 쌍의 최단 거리를 구하면 시간 복잡도는 다음과 같습니다.
- 다익스트라
- Linear Array 를 사용한 경우 0(V^3+VE) = 0(V^3)
- 우선 순위 큐(min-heap)을 사용한 경우 O((V^2)*logV+VE) - 벨만-포드
- O(V^2E) = O(V^4)
이보다 조금 더 빠르고 간단한 방법으로 모든 쌍 간의 최단 거리를 구하는 방법이 플로이드의 모든 쌍 최단 거리 알고리즘입니다.
플로이드 알고리즘은 그래프의 모든 정점 쌍의 최단 거리를 저장하는 2차원 배열 dist[ ][ ]를 계산하는 방식으로 동작합니다. 이 때, dist[u][v]는 u에서 v로 가는 최단 거리를 의미합니다.
플로이드 알고리즘은 경로의 경유점이라는 개념을 이용해서 동작합니다.
정점의 경유점
두 정점 u,v를 잇는 어떤 경로가 있고 그 경로는 시작점u와 끝점 v를 항상 지난다고 가정하겠습니다.
이 경로는 다른 정점들을 지나쳐 갈 수 있습니다. 그 이유는 u와 v를 직접 연결하는 간선이 없거나, 다른 정점을 경유해서 가는 경로가 전체 경로가 더 짧을 수 있기 때문입니다. 이 때 경로가 거쳐가는 정점들을 경유점이라고 합니다.
정점 집합 S에 포함된 정점만을 경유점으로 사용해서 u에서 v로 가는 최단 경로의 길이를 Ds(u,v)라고 하겠습니다.
S에 포함된 정점만을 경유점으로 사용해 u에서 v로 가는 최단 경로를 알고있다고 가정하겠습니다. S 중에 정점을 하나 골라서 x라고 하면, 최단 경로는 x를 경유할 수도 있고 경유하지 않을수도 있습니다.
- 경로가 x를 경유하지 않는다 : 이 경로는 S- {x} 에 포함된 정점들만을 경유점으로 사용합니다.
- 경로가 x를 경유한다 : 이 경로는 u에서 x로 가는 구간과 x에서 v로 가는 구간으로 나눌 수 있습니다. 이 2개의 부분 경로들은 각각 u와 x, x와 v를 잇는 최단 경로들이어야 합니다.
당연하게도 두 개의 부분 경로들은 x를 경유하지않으며, 따라서 S-{x}에 포함된 정점들만을 경유점으로 사용합니다.
S를 경유점으로 사용해 u에서 v로 가는 최단 경로는 위 2가지 중 더 짧은 경로가 될 것입니다.
Ds(u,v)를 다음과 같이 재귀적으로 정의할 수 있습니다.
위의 점화식을 살짝만 수정하면 모든 쌍에대한 최단 거리 문제를 동적 계획법으로 해결할 수 있습니다.
표기법을 살짝 고쳐서 Ck = Ds_k라 하면 다음과 같이 표현할 수 있습니다.
이 점화식은 C_k의 모든 값은 C(k-1)에만 의존하기 때문에 동적 계획법을 이용할 수 있습니다.
구현
구체적인 구현에 앞서 플로이드 알고리즘의 프로토타입은 다음과 같습니다.
d[k,i,j] = set{1,2,...,k} 에 포함되는 i에서 j 로 가는 최단 경로
k가 0인 경우에는 중간 경로 없는 vertex i에서 vertex j로 바로 가는 경로이기 때문에 d[0,i,j] = w[i,j] 입니다.
for(int k = 0;k<n;k++){
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
if(k == 0) d[k][i][j] = w[i,j];
else d[k][i][j] = min(d[k-1][i][j],d[k-1][i][k] + d[k-1][k][j]);
}
}
}위의 코드에서 볼 수 있듯 플로이드 알고리즘의 시간복잡도는 3중 for문을 돌기 때문에 O(|V|^3)입니다. 공간복잡도 역시 3차원 배열을 사용하기 때문에 (|V|^3) 입니다.
여기서 공간 복잡도를 줄일 수 있는 방법이 있습니다.
k번째 case를 계산할 때 k-1번째의 연산으로 부터 저장된 정보가 overwrite 될 수 있습니다. 그 이유는 출발점이나 도착점이 k번 정점일 때 사용 가능한 경유점의 목록에 k가 추가되는 것은 아무 의미가 없기 때문에, 이를 구분하지 않고 써도 되기 때문입니다.
예를 들면, 지하철 역에 들러 학교로 가는 최단 경로와 지하철역과 학교를 들러 학교로 가는 최단 경로는 똑같기 때문입니다.
이런 이유로 우리는 더이상 3차원 배열을 사용해서 k번째 연산과 k-1번째 연산을 구분할 필요없이 한 개의 2차원 배열을 이용해서 코드를 짤 수 있습니다.
for(int k = 0;k<n;k++){
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
d[i][j] = min(d[i][j],d[i][k] + d[k][j]);
}
}
}2차원 배열을 사용하면 시간 복잡도는 그대로지만 공간 복잡도는 O(|V|^3)에서 O(|V|^2)로 줄일 수 있습니다.
