[알고리즘] 그래프 8 - 최단 경로(플로이드)

최단 경로

플로이드 Floyd 최단 경로 알고리즘은 모든 정점 사이의 최단 경로 All to Shortest Path를 구하고 최단 경로로 만드는 알고리즘이다.

 

1. 초기 2차원 배열에 각 정점에서의 거리를 2차원 배열로 초깃값으로 집어넣는다.

2. 여기서부터 adj [v][w]=MIN(adj [v][w], adj [v][k]+adj [k][w])라는 식을 사용한다.

정점 0부터 k까지의 정점만을 이용한 정점 v에서 정점 w까지의 최단 경로를 의미하는데 정점 0부터 정점 k -1까지의 정점을 고려한 최단 거리 adj을 구한 상태에서 다음 정점 k를 정할 때, adj [v][w]와 adj [v][k] + adj [k][w] 중에서 작은 값을 최단 경로로 정한다.

 

 

 

#include <stdio.h>

#define INF  10000           // 무한대 값
#define MAX_VERTICES 5       // 그래프의 정점 개수

int A[MAX_VERTICES][MAX_VERTICES];			// k-최단 경로 배열

// 그래프 G11의 가중치 인접행렬
int weight[MAX_VERTICES][MAX_VERTICES] = {
    { 0, 10, 5, INF, INF },
    { INF, 0, 2, 1, INF },
    { INF, 3, 0, 9, 2 },
    { INF, INF, INF, 0, 4 },
    { 7, INF, INF, 6, 0 }
    //     //  A     B    C      D    E     F
    // {   0,    2,  INF,    4,  INF,  INF }, // A
    // {   2,    0,    4,    4,    3,    1 }, // B
    // { INF,    4,    0,  INF,  INF,    5 },  // C
    // {   4,    4,  INF,    0,    2,  INF },
    // { INF,    3,  INF,    2,    0,    5 },
    // { INF,    1,    5,  INF,    5,    0 }
}; 

// 최단 경로를 구하는 과정을 출력하는 연산
void printStep(int step) {
    int i, j;
    printf("\n A%d : ", step);
    
    // 각 정점에 대한 최단 경로 출력
    for (i = 0; i < MAX_VERTICES; i++) {
        printf("\t");
        for (j = 0; j < MAX_VERTICES; j++) {
            // 무한대 값인 경우 '*' 출력, 아니면 최단 경로 값 출력
            if (A[i][j] == INF)
                printf("%4c", '*');
            else printf("%4d", A[i][j]);
        }
        printf("\n\n");
    }
}

// [알고리즘 8-4] 구현
void Floyd_shortestPath(int n) {
    int v, w, k, step = -1;

    // 초기화
    for (v = 0; v < n; v++)
        for (w = 0; w < n; w++)
            A[v][w] = weight[v][w];

    printStep(step);

    // k를 경유지로 하는 최단 경로 계산
    for (k = 0; k < n; k++) {
        for (v = 0; v < n; v++)
            for (w = 0; w < n; w++)
                // 현재까지의 최단 경로보다 더 짧은 경로가 있으면 업데이트
                if (A[v][k] + A[k][w] < A[v][w])
                    A[v][w] = A[v][k] + A[k][w];
        
        printStep(++step);
    }
}

int main(void) {
    int i, j;
    extern int weight[MAX_VERTICES][MAX_VERTICES];

    // 가중치 인접 행렬 출력
    printf("\n ********** 가중치 인접 행렬 **********\n\n");
    for (i = 0; i < MAX_VERTICES; i++) {
        for (j = 0; j < MAX_VERTICES; j++) {
            // 무한대 값인 경우 '*' 출력, 아니면 가중치 값 출력
            if (weight[i][j] == INF)
                printf("%4c", '*');
            else printf("%4d", weight[i][j]);
        }
        printf("\n\n");
    }

    // 플로이드 최단 경로 알고리즘 수행
    printf("\n ********* 플로이드 최단 경로 구하기 *********\n\n");
    Floyd_shortestPath(MAX_VERTICES);

    getchar();  // 프로그램 종료를 위한 입력 대기
    return 0;
}