CODERJH

Floyd의 최단 경로 알고리즘 본문

컴퓨터 알고리즘 연습

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;
}

 

 

참고문헌

http://book.naver.com/bookdb/book_detail.naver?bid=14566230

 

저작자표시