그래프 - Floyd 알고리즘

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다.

# 해당 게시글에 대한 모든 피드백 환영합니다. 

Floyd 알고리즘

그래프에 존재하는 모든 정점 사이의 최단 경로를 한번에 모두 찾아주는 알고리즘

 

Dijkstra 알고리즘에서는 '하나의 정점'에서 '다른 모든 정점'으로의 최단 경로를 찾았다면,

Floyd 알고리즘에서는 '모든 정점'에서 '모든 정점'으로의 최단 경로를 구할 수 있다. 

 

즉, 그래프의 모든 정점에 대한 최단 경로쌍을 구할 수 있다.

 

이 알고리즘의 핵심 원리는 '거쳐가는 정점'을 기준으로 최단 경로를 구한다. 

 

알고리즘

floyd(G):
    for k<-0 to n-1
        for i<-0 to n-1
            for j<-0 to n-1
                A[i][j] = min(A[i][j], A[i][k] + A[k][j])

생각의 순서

1. 하나의 정점에서 다른 정점으로 갈 때, 바로 갈 수 있으면 '기존 인접행렬 값'으로, 바로 갈 수 없으면 '무한'으로 배열에 값을 저장한다.

2. 3중 for문을 통해 거쳐가는 정점을 설정한 후, 특정 정점을 거칠 때 비용이 줄어드는 경우에는 배열의 값을 변경한다.

3. 위의 과정을 반복해 모든 정점 사이의 최단 경로를 탐색한다.

 

이를 c언어로 구현해보고, 모니터링을 통해 이해해보면 좋을 것 같다.

 

c언어로 구현

#define def_floyd
 
#ifdef def_floyd
 
#include <stdio.h>
#include <stdlib.h>
 
#define TRUE 1
#define FALSE 0
 
#define MAX_VERTICES 50
#define INF 999
 
typedef struct GraphType {
    int n;
    int weight[MAX_VERTICES][MAX_VERTICES];
} GraphType;
 
int A[MAX_VERTICES][MAX_VERTICES];
 
void printA(GraphType* g) {
    int i, j;
 
    printf("=============================\n");
    for (i = 0; i < g->n; i++)
    {
        for (j = 0; j < g->n; j++)
        {
            if (A[i][j] == INF) {
                printf(" * ");
            } else {
                printf("%3d", A[i][j]);
            }
        }
        printf("\n");
    }
    printf("=============================\n");
}
 
void floyd(GraphType* g) {
    int i, j, k;
 
    for (i = 0; i < g->n; i++) {
        for (j = 0; j < g->n; j++) {
            A[i][j] = g->weight[i][j];
        }
    }
    printA(g);
 
    for (k = 0; k < g->n; k++)
    {
        for (i = 0; i < g->n; i++)
        {
            for (j = 0; j < g->n; j++)
            {
                if (A[i][j] > A[i][k] + A[k][j])
                    A[i][j] = A[i][k] + A[k][j];
            }
        }
        printA(g);
    }
}
int main()
{
    GraphType g = { 4,
        {{0, 5, INF, 8},
        {7, 0, 9, INF},
        {2, INF, 0, 4},
        {INF, INF, 3, 0}
        }
    };
    floyd(&g);
    return 0;
}
#endif

결과

시간복잡도

O(n^3)