플로이드 알고리즘 구현 방법 알려주시면 감사하겠습니다

안녕하세요..

​

흥미로운 주제의 문의가 있었군요.

늦은 답변이라 이미 해답을 찾았을 지 모르겠으나..

아래와 같이 소스코드와 출력 캡쳐와 함께 답변을 드려 봅니다.

도움이 되시길 바랍니다.

​

추가) macos clang 기준으로 작성된 것이므로 만일 윈도우 버전이면, ansi 관련 코드 등은 호환 되지 않을 수 있습니다.

해당 부분만 제거 하시면되겠습니다.

## 소스 코드 파트 ##

void Floyd_City() { const int INF = 1000000000; // 비교를 위한 비교적 큰값설정, 교체값 const int size = 11; // 열이름 표시를 위해 1을 더함 char City[][8] = {"서울", "원주", "강릉", "포항", "천안", "논산", "대전", "광주", "대구", "부산"}; // 거리표 int dist[size][size]; // 인접행렬 int adj[size][size]; for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { adj[i][j] = 0; } } adj[1][2] = 15; adj[1][5] = 12; adj[2][1] = 15; adj[2][3] = 21; adj[2][9] = 7; adj[3][2] = 21; adj[3][4] = 25; adj[4][3] = 25; adj[4][9] = 19; adj[4][10] = 5; adj[5][1] = 12; adj[5][6] = 4; adj[5][7] = 10; adj[6][5] = 4; adj[6][7] = 3; adj[6][8] = 13; adj[7][5] = 10; adj[7][6] = 3; adj[7][9] = 10; adj[8][6] = 13; adj[8][10] = 15; adj[9][2] = 7; adj[9][4] = 19; adj[9][7] = 10; adj[9][10] = 9; adj[10][4] = 5; adj[10][8] = 15; adj[10][9] = 9; // 초기화 (같은도시 : 0, 연결되지 않은 도시 : 무한대, 나머지 : 거리(adj)) for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { if (i == j) { dist[i][j] = 0; } else if (adj[i][j] != 0) { dist[i][j] = adj[i][j]; } else { dist[i][j] = INF; } } } printf("\n"); // 초기 거리 출력 printf("\u2728 \033[33m 도시별 거리 출력 표 \033[0m \u2728\n"); for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { if (dist[i][j] == INF) { printf(" %s ", "\u221E"); continue; } printf("%2d ", dist[i][j]); } printf("\n"); } printf("\n"); // 최단거리 계산 (플로이드 워셜 알고리즘) for (int k = 0; k < size; k++) { for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { int temp = dist[i][k] + dist[k][j]; if (dist[i][j] > temp) { dist[i][j] = temp; } } } } printf("\n"); // 최단거리 출력 표 (도시이름과 함께 출력) printf("\u2728 \033[33m 최단거리 출력 표 (도시이름과 함께 출력) \033[0m \u2728\n"); for (int i = 0; i < size; i++) { if (i == 0) { printf("\t"); for (int j = 0; j < size - 1; j++) { printf("\033[32;42m %s \033[0m\t", City[j]); } printf("\n"); continue; } for (int j = 0; j < size; j++) { if (j == 0) { printf("\033[32;42m %s \033[0m\t", City[i - 1]); continue; } printf("%4d\t", dist[i][j]); } printf("\n"); } printf("\n"); // From ~ To : 최단거리 출력 (도시이름과 함께 출력) printf("\u2728 \033[33m From ~ To : 최단거리 출력 (도시이름과 함께 출력) \033[0m \u2728\n"); for (int i = 0; i < size; i++) { if (i != 0) { printf("\u26DF "); } for (int j = 0; j < size; j++) { if (dist[i][j] == INF) { continue; } if (i == j) continue; printf("\033[31m %s\u27A0%s \u276A%2dkm\u276B,\033[0m ", City[i - 1], City[j - 1], dist[i][j]); } printf("\n"); } } int main() { Floyd_City(); }

## 출력 테스트 ##

## 참조 데이터 ##

## 제공된 이미지 데이터 ##

​