행렬 알고리즘) 워셜 알고리즘

사용언어 : C++

 

- 워셜 알고리즘은 관계의 전이 폐쇄를 구하는 효율적인 방법이다. 여기서 관계란 n * n 행렬을 말하고, 이 행렬의 전이 폐쇄를 구하는 알고리즘 중 하나가 워셜 알고리즘이다.

 

- 여기서 폐쇄란, R이 행렬 A에 대한 관계이고, 만약 어떤 특성 P(대칭, 전이, 반사)를 가지지 않는다면 R을 포함하면서 특성 P를 만족시키는 A에 대한 가장 작은 관계 S를 말한다. 고로 전이 폐쇄는, 전이 특성을 포함하는 가장 작은 관계 S를 말한다.

워셜 알고리즘의 의사코드

W := M
for k := 1 to n
	for i := 1 to n
    	for j := 1to n
        W(i,j) := W(i,j) or ( W(i,k) and W(k,j) )
return W{ W = [w(i,j) is M(R*)] }

 

워셜 알고리즘 C++ 코드

void Warshall() {
	int arr[4][4] = { {0,0,0,1},{1,0,1,0},{1,0,0,1},{0,0,1,0} };
	//int arr[4][4] = { {0,1,0,0},{1,0,1,0},{0,0,0,1},{1,0,0,0} };
	for (int k = 0; k < 4; k++) {
		for (int i = 0; i < 4; i++) {
			if (k == i)			// 똑같은 부분 건너뛰기.
				continue;
			else if (arr[i][k] == 1) {		// 만약 arr[i][k] 행렬이 1이라면 arr[k]로 가는 관계가 잇음. 따라서 arr[k]를 판별
				for (int j = 0; j < 4; j++) {	// arr[k][j] 행렬이 1이라면 arr[i][j]로 가는 전이 관계가 존재하여 추가.
					if (arr[k][j]) {
						arr[i][j] = 1;
					}
				}
			}
		}
		cout << "W[" << k << "] : " << endl;
		for (int i = 0; i < 4; i++) {
			for (int j = 0; j < 4; j++) {
				cout << arr[i][j] << " ";
			}
			cout << endl;
		}
	}
}

왼쪽과 같이 작동하는 코드를 볼 수 있다.