[c++] Floyd의 알고리즘 - 가중치가 다른 길찾기

문제는 다음과 같다. 가중치가 같은 최단 경로의 알고리즘으로는 BFS를 사용할 수 있지만 이 같은 경우에서는 경로마다 가중치가 다르기 때문에 BFS로 접근하면 안된다. 대신 DP 다이나믹 프로그래밍을 사용하여 부분 최적해를 구해가며 진행할 수 있겠다. 

---

1. map만들기 

우선 배열에 map을 만들어주어야 한다. 이 때 중요한 것은 갈 수 없는 방향에 대해서는 infinite한 값- 매우 큰 값으로 이루어져야 한다는 것이다. 

따라서 위의 그래프를 이용해 map을 만들면 다음과 같다. 

int w[6][6] = {
	{0,0,0,0,0,0},
	{0,0,1,1000,1,5},
	{0,9,0,3,2,1000},
	{0,1000,1000,0,4,1000},
	{0,1000,1000,2,0,3},
	{0,3,1000,1000,1000,0},
};

infinite한 값을 1000 으로 설정해주었고 인덱스를 1서부터 시작하기 위해 0으로 채워진 열과 행을 하나씩 추가해주었다. 

예를 들어 위의 map에서 2행 3열에 해당하는 값은 1인데 이는 1에서 2로 가는 가중치에 해당한다. ( 0으로 채워진 열과 행이 하나씩 추가 되었기 때문이다. ) 

---

2. Floyd의 알고리즘 

int D[6][6];
int p[6][6];

void floyd2(int n, int w[][6], int D[][6], int p[][6]) {
	int i, j, k;
	//초기화 
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			p[i][j] = 0;
			D[i][j] = w[i][j];
		}
	}
	//for (int i = 1; i <= 5; i++) {
	//	for (int j = 1; j <= 5; j++) {
	//		cout << D[i][j] << " ";
	//	}
	//	cout << "\n";
	//}
	//cout << "\n";
	for (k = 1; k <= n; k++) {// 가로
		for (int i = 1; i <= n; i++) {//세로
			for (int j = 1; j <= n; j++) {
				if (D[i][k] + D[k][j] < D[i][j]) {//k를 거쳐가는 경로의 합이 더 작다면 
					p[i][j] = k; // 경로에 k를 저장해준다. 바로 가면 0
					D[i][j] = D[i][k] + D[k][j]; // Distance에는 아까 구한 더 작은 값을 넣어준다. 
				}
			}
		}
	}
}

Floyd의 알고리즘을 c++로 구현하면 다음과 같다. 우선 경로를 저장할 배열인 p와 최단 경로를 저장할 배열인 D를 선언해준다. 

그 후 for문을 돌면서 D배열을 아까 선언한 map의 값으로 초기화를 해준다.  

DP를 사용하지 않으면 모든 경우의 수를 탐색해야 하는 경우의 수인 n!에 해당하겠지만 DP를 통해 n^3으로 줄일 수 있다. 

for문을 돌면서 우리는 부분 최적해를 구해야한다. 즉 1에서 2를 갈 때 최적의 distance를 구해 저장해두고 이를 다시 이용해 1->3을 갈 때는 1->2의 최적해를 이미 알고 있으니 2->3의 최적해만 구해 원래 있던 값에 더해주면 되는 것이다. 

 

삼중 for문을 잘 살펴보자

	for (k = 1; k <= n; k++) {// 가로
		for (int i = 1; i <= n; i++) {//세로
			for (int j = 1; j <= n; j++) {
				if (D[i][k] + D[k][j] < D[i][j]) {//k를 거쳐가는 경로의 합이 더 작다면 
					p[i][j] = k; // 경로에 k를 저장해준다. 바로 가면 0
					D[i][j] = D[i][k] + D[k][j]; // Distance에는 아까 구한 더 작은 값을 넣어준다. 
				}
			}
		}
	}

여기 인덱스에서 i는 시작점 j는 도착점 k는 경유점에 해당한다. 모든 경우를 for문을 통해 1에서 5까지 돌면서 if문을 통해 비교해준다. 이 때 비교하는 조건은 i에서 j를 가는데 k점을 거쳐서 가는 것과 바로 직행해서 가는 경우를 비교하는 것이다. 만약 거쳐서 가는 것이 더 적게 걸린다면 distance matrix를 k를 거쳐서 가는 거리로 초기화 해주고 path배열에도 k를 넣어준다. 

---

3. 경로 출력 

void path(int i, int j) {
	/*if (cnt <= 1) {
		cnt++;
		cout << "The Shortest Path("  <<i << ", " << j << ") v" << i << "->";
	}*/
	if (p[i][j] != 0) {	
		path(i, p[i][j]);
		cout << "v" << p[i][j] << "-> ";
		path(p[i][j], j);
	}
}

경로 출력 알고리즘은 다음과 같다. 앞서 path를 저장해주었던 p의 배열을 돌면서 만약 거쳐서 가는 경우가 더 작은 경우 k를 path에 저장했었다. 이를 이용해 만약 k가 존재한다면 그 k를 따라가면서 0이 나올 때까지 출력을 반복한다. 

---

3. 결과

main문에 5에서 3으로 가는 경우 1에서 3으로 가는 경우 2에서 5로 가는 경우의 최적 해를 출력해보겠다. main문은 다음과 같다. 

int main() {
	int n = 5;
	floyd2(n, w, D, p);
	cout << "D배열" << "\n";

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << D[i][j] << " ";
		}
		cout << "\n";
	}
	cout << "\n";
	cout << "p배열" << "\n";
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << p[i][j] << " ";
		}
		cout << "\n";
	}
	printPath(5, 3);
	printPath(1, 3);
	printPath(2, 5);
}

정상적으로 path와 경로가 출력된다.