학사 나부랭이
Floyd algorithm 본문
#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