[자료구조] 플로이드(Floyd)의 최단 경로 알고리즘

 

Floyd의 최단 경로 알고리즘

최단 경로를 찾는 과정은 다음과 같습니다.

1. 각각의 정점이 다른 정점으로 가는 최소 가중치를 저장
2. 무작위의 두 정점 사이의 가중치와 그 두 정점 사이에 특정 정점을 거쳐서 가는 가중치를 비교해서 가장 가중치가 적은 간선으로 갱신
3. 모든 노드를 방문할 때까지 2번을 반복

예시로 한 그래프를 Floyd의 알고리즘을 이용해 최단 경로를 구해보겠습니다.

 

Floyd 알고리즘 또한 시작 정점에서 다른 정점으로 가는 최단거리를 기록하는 배열이 필요합니다.

 

각 정점에서 다른 정점으로 이동할 때 걸리는 가중치를 표로 표현한 것입니다.

표 위의 그래프와 비교해봅시다. 예를 들어, 0번 정점과 2번 정점의 간선 가중치를 확인해보면 23인 것을 알 수 있습니다. 또한 무방향 그래프를 표에 옮겼으므로 위 아래가 대칭임을 파악할 수 있습니다. 편의를 위해 아래쪽 배열만 사용하겠습니다.

정점 0부터 차례대로 해당 정점을 거치는 간선과 거치지 않는 간선을 비교해주면 됩니다.

 

이를 구현하면 아래와 같습니다.

typedef struct Graph {
    int n; // 정점의 개수
    int weight[MAX_VERTICES][MAX_VERTICES];
} Graph;

int A[MAX_VERTICES][MAX_VERTICES];

void printA(Graph *g) {
    printf("=====================================\n");
    for(int i = 0; i < g->n; i++) {
        for(int j = 0; j < g->n; j++) {
            if(A[i][j] == INF) {
                printf("   * ");
            } else printf("%4d ", A[i][j]);
        }
        printf("\n");
    }
    printf("=====================================\n");
}

void floyd(Graph *g) {
    for(int i = 0; i < g->n; i++) {
        for(int j = 0; j < g->n; j++) {
            A[i][j] = g->weight[i][j];
        }
    }
    printA(g);

    for(int k = 0; k < g->n; k++) {
        for(int i = 0; i < g->n; i++) {
            for(int j = 0; j < g->n; j++) {
                if(A[i][k] + A[k][j] < A[i][j]) {
                    A[i][j] = A[i][k] + A[k][j];
                }
            }
        }
        printA(g);
    }
}