Floyd's Algorithm

학교에서 Floyd's 알고리즘을 배웠고, 과제로 자유로운 언어로 해당 알고리즘을 구현하는 것이 나왔다. 나는 C++를 이용했다.

#include <iostream>
#include <vector>
using namespace std;

const int num = 5;
const int NON = 10000;
vector<vector<int>> W = {
	{0,3,6,NON,4},
	{NON,0,2,NON,4},
	{5,1,0,2,NON},
	{NON,5,NON,0,1},
	{NON,NON,NON,3,0}
};
vector<vector<int>> D(num, vector<int>(num,NON));
vector<vector<int>> P(num, vector<int>(num,0));
vector<vector<int>> makeD() {
	D = W;
	for (int k = 0; k < num; k++) {
		for (int i = 0; i < num; i++) {
			for (int j = 0; j < num; j++) {
				if (D[i][k] + D[k][j] < D[i][j])
					D[i][j] = D[i][k] + D[k][j];
			}
		}
	}
	return D;
}
vector<vector<int>> makeP() {
	
	D = W;
	for (int k = 0; k < num; k++) {
		for (int i = 0; i < num; i++) {
			for (int j = 0; j < num; j++) {
				if (D[i][k] + D[k][j] < D[i][j]) {
					D[i][j] = D[i][k] + D[k][j];
					P[i][j] = k + 1;
				}
			}
		}
	}
	return P;
}
void floyd() {
	vector<vector<int>> d = makeD();
	vector<vector<int>> p = makeP();
	cout << "<D>" << endl;
	for (int i = 0; i < num; i++) {
		for (int j = 0; j < num; j++)
			cout << d[i][j] << ' ';
		cout << endl;
	}
	cout << "<P>" << endl;
	for (int i = 0; i < num; i++) {
		for (int j = 0; j < num; j++)
			cout << p[i][j] << ' ';
		cout << endl;
	}
}
void path(int q, int r) {
	vector<vector<int>> p = makeP();
	int a = q - 1;
	int b = r - 1;

	if (p[a][b] != 0) {
		path(a+1, p[a][b] );
		cout << " v" << p[a][b];
		path(p[a][b] , b+1);
	}
	else
		return;
}
int main() {
	floyd();
	cout << "<path>" << endl;
	path(2, 4);
	return 0;
}

노드에서 시작하는 것은 시간 부족으로 하지 못했구,, 다음에 시간 나면 해봐야겠다