컴퓨터 알고리즘 연습
Floyd의 최단 경로 알고리즘
CODERJH
2022. 5. 10. 23:57
Floyd의 최단 경로 알고리즘은 그래프에 존재하는 모든 정점 사이의 최단 경로를 한번에 모두 찾아주는 알고리즘이다.
| #include <stdio.h> #include <stdlib.h> #define INF typedef struct FloydGraph { int n; int weight[100][100]; } FloydGraph; int cnt; int distance[100][100]; void GraphPrint(FloydGraph* f) { int i, j; printf("--> %d 번째\n\n",++cnt); for (i = 0; i < f->n; i++) { for (j = 0; j < f->n; j++) { if (distance[i][j] == INF) printf(" * "); else printf("%3d ", distance[i][j]); } printf("\n"); } printf("\n"); } void floyd(FloydGraph* f) { int i, j, k; for (i = 0; i < f->n; i++) for (j = 0; j < f->n; j++) distance[i][j] = f->weight[i][j]; GraphPrint(f); for (k = 0; k < f->n; k++) { for (i = 0; i < f->n; i++) for (j = 0; j < f->n; j++) if (distance[i][k] + distance[k][j] < distance[i][j]) distance[i][j] = distance[i][k] + distance[k][j]; GraphPrint(f); } } int main()
{ int n; FloydGraph city = { 10, {{ 0,15,INF,12,INF,INF,INF,INF,INF,INF}, {15,0,21,INF,INF,INF,7,INF,INF,INF}, {INF,21,0,INF,INF,INF,INF,25,INF,INF}, {12,INF,INF,0,4,10,INF,INF,INF,INF}, {INF,INF,INF,4,0,3,INF,INF,13,INF}, {INF,INF,INF,10,3,0,10,INF,INF,INF}, {INF,7,INF,INF,INF,10,0,19,INF,9}, {INF,INF,25,INF,INF,INF,19,0,INF,5}, {INF,INF,INF,INF,13,INF,INF,INF,0,15}, {INF,INF,INF,INF,INF,INF,9,5,15,0}} }; printf(" 0=서울, 1=원주, 2=강릉, 3=천안, 4=논산, 5=대전, 6=대구, 7=포항, 8=광주, 9=부산\n\n"); floyd(&city); return 0; } |
참고문헌
