학사 나부랭이

Floyd algorithm 본문

塵箱/코드 삽질

Floyd algorithm

태양왕 해킹 (14세) 2021. 4. 16. 14:16
#include <iostream>
using namespace std;
int min(int i, int j1, int j2) {
	if ((i < j1 + j2 && i != -1) || j1 == -1 || j2 == -1) return i;
	else return j1 + j2;
}
void path(int q, int r, int p[][6]) {
	if (p[q][r] > -1) {
		path(q, p[q][r], p);
		cout << "v" << p[q][r] << " ";
		path(p[q][r], r, p);
	}
}
void print(int(*d)[6]) {
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < 6; j++) {
			cout.width(3);
			cout.fill(' ');
			cout << d[i][j];
		}
		cout << endl;
	}
	system("pause");
	system("cls");
}
void print(int(*d)[6], int(*p)[6]) {
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < 6; j++) {
			cout.width(3);
			cout.fill(' ');
			cout << d[i][j];
		}
		cout.width(3);
		cout.fill(' ');
		cout << "	|	";
		for (int j = 0; j < 6; j++) {
			cout.width(3);
			cout.fill(' ');
			cout << p[i][j];
		}
		cout << endl;
	}
	system("pause");
	system("cls");
}
void floyd(int n, int(*d)[6], int(*p)[6]) {
	int i, j, k, tmp;
	for (k = 0; k < n; k++) {
		for (i = 0; i < n; i++) {
			for (j = 0; j < n; j++) {
				tmp = min(d[i][j], d[i][k], d[k][j]);
				if (tmp < d[i][j] || (d[i][j] == -1 && tmp != -1)) p[i][j] = k;
				d[i][j] = tmp;
			}
		}
		if (k < n - 1) {
			cout << "D" << k << "				P" << k << endl;
			print(d, p);
		}
	}
}
int main() {
	int d[6][6] = { {0, 7, -1, 11, -1, -1}, {3, 0, -1, -1, 17, -1}, {-1, 6, 0, -1, -1, -1}, {-1, -1, -1, 0, 9, -1}, {-1, 5, 15, 16, 0, 2}, {-1, -1, 11, -1, 8, 0} };
	int p[6][6];
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < 6; j++) {
			if (d[i][j] == -1) p[i][j] = -3;
			else if (d[i][j] == 0)p[i][j] = -2;
			else p[i][j] = -1;
		}
	}
	cout << "==========================Floyd Algorithm==========================\nnode index: 0 ~ 5, disconnected weight: -1\ndisconnected path: -3, self path: -2, direct path: -1\nPress any key to start." << endl;
	system("pause");
	system("cls");
	cout << "W" << endl;
	print(d);
	floyd(6, d, p);
	cout << "Results(D5 | P5)" << endl;
	print(d, p);
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < 6; j++) {
			if (p[i][j] > -2) {
				cout << "v" << i << " ";
				path(i, j, p);
				cout << "v" << j << endl;
			}
		}
	}
	return 0;
}

'塵箱 > 코드 삽질' 카테고리의 다른 글

백준 15829 - 모듈러 연산  (0) 2021.04.20
백준 10866 - 덱  (0) 2021.04.19
백준 1494 - 다이나믹 프로그래밍, 이진 탐색  (0) 2021.04.17
백준 2164 - 큐 구현  (0) 2021.04.16
Strassen function  (0) 2021.04.04
Comments