7. 최단 경로 알고리즘 - Floyd 알고리즘

플로이드 알고리즘은 다익스트라나 벨만-포드 알고리즘과 다르게 

모든 정점 쌍에 대해 둘 사이의 최단 거리를 구하는 모든 쌍 최단거리 알고리즘이다.

플로이드 알고리즘의 작동 원리를 이해하기 위해 정점 u, v에 대해 둘 사이를 잇는 최단 경로를 구한다고 해보자.

이 때 이 경로에는 다른 정점들이 포함될 수도 있고, 포함되지 않을수도 있다.

정점 집합 S에 포함된 정점만을 경유점으로 사용해 u에서 v까지 가는 최단 경로의 길이를 Cs(u, v) 라고 하자.

이 때 집합의 모든 정점들을 경유점으로 사용해야 하는 것은 아니다.

그러면 집합 S에 포함된 정점 하나를 x라고 하면, u에서 v까지의 최단 경로는 x를 포함할수도, 포함하지 않을 수도 있다.

이 때 최단 경로는 다음 두가지 형태를 가진다.

1. 경로가 정점 x를 경유한다. 

-> 이 경로를 u에서 x로 가는 구간과 x에서 v로 가는 구간으로 나눌 수 있다.

이 때 이 두개의 구간은 각각 최단 경로여야 한다. 또한, 두개의 경로는 x를 경유하지 않으므로 S-{x} 에 포함된 정점만을 경유한다.

2. 경로가 정점 x를 경유하지 않는다.

-> 이 경로는 S-{x} 에 포함된 정점만을 경유한다.

u에서 v까지 가는 최단 경로는 위의 두가지 경우 중 더 짧은 경로가 될 것이다.

따라서 다음과 같이 재귀적으로 정의할 수 있다.

Ds(u, v) = min(Ds-x(u, v), Ds-x(u, x) + Ds-x(x, v))

위의 점화식을 활용하여 각 정점을 0번부터 k-1번까지 번호 매기고 정점 집합을 점점 늘려가면서 

해당 정점을 경유점으로 했을 때의 모든 쌍의 최단 경로를 계산하도록 한다.

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

int v;  // 정점의 개수

int adj[MAX_V][MAX_V];  // 그래프의 인접 행렬

int c[MAX_V][MAX_V][MAX_V];  

void allPairShortestPath(){

// c[0][][]에 대해 초기화

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 = 0; 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]);

}

}

}

}

위의 코드에서 그래프의 인접 행렬을 표현할 때 두 정점 사이에 간선이 없다면 아주 큰 값을 넣어두어야 한다.

이 큰 값은 실제 존재하는 어떤 경로의 길이보다도 커야한다.

위의 코드는 사용하는 배열의 크기가 너무 커 메모리 사용에 있어서 비효율적이다.

그런데 어차피 c[k][i][j]를 계산할 때, c[k-1][][]에 대해서만 필요하므로 슬라이딩 윈도우 기법을 사용하여 배열 크기를 2*|V|*|V|로 줄일 수 있다.

혹은 별도의 배열을 사용하지 않고 인접 행렬에 바로 저장하는 방법 또한 있다.

어떻게 그게 가능할까?

점화식에서 필요한 값은 c[k-1][i][k] 와 c[k-1][k][j] 이다. 이 값들과 c[k][i][k] 와 c[k][k][j]는 얼마나 다를까?

c[k-1][i][k] 의 의미는 k-1번 정점까지를 경유점으로 사용해 i번 정점 부터 k번 정점까지 가는 최단 경로의 길이이다.

c[k][i][k]의 의미는 k번 정점까지를 경유점으로 사용해 i번 정점부터 k번 정점까지 가는 최단 경로의 길이이다.

즉, k번 정점이 시작점이나 종료점일 경우에는 정점 집합에 포함되어있든 되어있지 않든 아무 의미가 없다.

즉, c[k-1][i][k]를 c[k][i][k]로 대신해서 쓸 수 있다는 것이다.

따라서 c[k%2]와 c[(k-1)%2]로 구분지을 필요없이 하나의 이차원 배열에 섞어 써도 된다.

위의 점화식에서 c[k-1][i][j]의 경우는 결국 k반복문의 바로 이전 계산값을 의미하므로, adj[i][j]로 대신해서 쓸 수 있다.

현재 adj[i][j]에는 이전 k반복문, 즉 k-1이었을 때의 값을 저장하고 있기 때문이다.

// 플로이드 알고리즘

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][i] = min(adj[i][j], adj[i][k] + adj[k][j]);

}

}

}

}

실제 경로 계산하기

실제 경로를 계산하기 위해서는 각 정점의 쌍 u, v 에 대해 마지막으로 adj[u][v]를 갱신했을 때 사용했던 k의 값을 저장해두면 된다.

k번 정점을 경유해서 최단 경로 길이가 나왔다는 의미는, 두 정점을 연결하는 최단 경로에 k번 정점이 포함되어 있다는 뜻이기 때문이다.

따라서 재귀호출을 이용해 u에서 k로 가는 최단 경로를 찾고, k에서 v로 가는 최단 경로를 찾아 둘을 합치면

u에서 v로 가는 최단 경로를 찾을 수 있다.

// 플로이드 알고리즘에서 실제 경로 계산하기

int v;

int adj[MAX_V][MAX_V];

int via[MAX_V][MAX_V];

void floyd(){

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]){

adj[i][j] = adj[i][k] + adj[k][j];

via[i][j] = k;

}

}

}

}

}

void reconstruct(int u, int v, vector<int>& path){

// base case : 해당 경로 사이에 어떤 경유점도 존재하지 않으면 시작점과 끝점을 경로에 저장

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);

}

}