sakuragi's miscellaneous space

 아무래도 최근에 가장 많은 시간을 할애하고 있는 것이 이 알고리즘 수업의 과제이다 보니, 자꾸만 포스팅이 이런 내용만 쓰게 된다. 이번의 과제는 알고리즘 자체는 어려운 것이 아니였고, 교수님이 그려주신 그래프를 보고, 플로이드의 최단 경로를 구하는 알고리즘으로 구하는 것이였다.
  옆의 그림이 가중치 방향성 그래프인데, 예를 들면, v3에서 v1으로 가는 가중치(거리/비용)가 -1 이고, v1에서 v3로 직접 가는 방법은 없다는 의미이다. v1에서 v3 로 가기 위해서는 v1 -> v2 -> v3 의 방법①과 v1 -> v2 -> v4 -> v3 의 방법②가 존재하는데 이런 여러 경로 중에서 가중치의 합이 가장 적은 경로를 구하는 것이다. 방법① 경로는 -1 + 2 + 4 = 5가 되고, 방법② 경로는 -1 + 2 + 3 + 7 = 11이 된다. 그러므로 최종적으로 최단 경로는 v1 -> v2 -> v3(방법①)가 된다.

 플로이드 알고리즘은 우선 옆의 그래프를 W 라고 하는 행렬(배열)에 저장한 후에, 플로이드 최단경로 알고리즘(함수)을 실행하면서 최단경로를 D라는 행렬(배열)에다가 점점 최단경로의 값으로 갱신해 나간다(자세한 설명은 "플로이드 알고리즘" 이라고만 검색해도 많이 나오니 참고). 어째든 이번 과제는 이 "최단경로를 구하는 플로이드 알고리즘"이였다.
플로이드 알고리즘 소스에서 쓰일 텍스트 파일(floyd_array.txt)

4
0 2 99 99
5 0 4 3
-1 99 0 4
99 1 7 0

최단경로를 구하는 플로이드 알고리즘 소스

#include <stdio.h>
#include <malloc.h>

int** make_array(int n);    // 배열 동적 메모리 할당
void read_array(int *D[], int n);   // 파일에서 배열 값 읽음
void print_array(int* D[], int n);  // 배열값 출력
int** floyd(int* W[],int* P[], int n);  // 플로이드 최단 경로 알고리즘
void print_path(int *P[], int q, int r);    // 최단경로 출력

FILE* file; // 배열을 읽기 위한 파일 식별자

int main()
{
    int q, r, n;
    int **D, **W, **P; // 프로그램에서 쓰일 배열

    file = fopen("floyd_array.txt", "r");  // 배열 값을 담고 있는 파일
    if(file == NULL) {
        perror("File open error");
        return 0;
    }

    fscanf(file, "%d", &n);    // 배열의 행과 열의 수 N x N

    W = make_array(n);  // N x N 행렬을 메모리에 할당
    read_array(W, n);   // 파일로 부터 W 행렬에 값 입력
    printf("Ployd Shortest Path Algorithm\nW weight array :\n");
    print_array(W, n);  // W 행렬 출력

    printf("\n");

    P = make_array(n+1);   // 경로 출력을 원활히 하기 위해 0번째 행과 열을 쓰지 않음
    D = floyd(W, P, n); // 플로이드 최단 경로 알고리늠 실행해서 결과 행렬을 D 행렬에 입력
    printf("D shortest array :\n");
    print_array(D, n);  // 결과 D 행렬 출력(K값에 따른 배열 출력시 생략)

    printf("\nStart vertex(1 ~ %d) : ", n);    // 출력할 경로의 시작, 끝점 입력
    scanf("%d", &q);
    printf("End vertex(1 ~ %d) : ", n);
    scanf("%d", &r);
    if ( q <= 0 || r <= 0 || q > n || r > n) { // 시작,끝을 벗어나면 에러
        printf("Error : Plz, Input number 1 ~ %d\n", n);
        return 0;
    }

    printf("\n");  // 입력받은 시작점과 끝점 간의 최단 경로 출력
    printf("Shortest Path from v%d to v%d\n  : v%d -->", q, r, q);
    print_path(P, q, r);
    printf(" v%d\n", r);
    printf("Distance : %d\n", D[q-1][r-1]);    // 거리 출력

    free(D);    // 사용한 메모리 해제
    free(W);
    free(P);
    fclose(file);   // 열었던 파일을 닫아줌

    return 0;
}

int** make_array(int n) // n x n 행렬의 메모리를 할당후 배열의 시작 주소를 반환
{
    int i;
    int** array;
    array = (int**)malloc(sizeof(int*)*n);
    for(i = 0; i < n; i++)
        array[i] = (int*)malloc(sizeof(int)*n);

    return array;
}

void read_array(int *D[], int n)    // 파일로 부터 행렬 입력 받음
{
    int i, j;
    for(i = 0; i < n; i++) {
        for( j = 0; j < n; j++) {
            fscanf(file, "%d", &D[i][j]);
        }
    }
}

void print_array(int* D[], int n)   // 지정된 배열의 값을 출력
{
    int i, j;

    for (i = 0; i < n; i++) {
        for(j = 0; j < n; j++) {
            if( D[i][j] == 99 )  // 99 이면 무한대의 의미로 oo를 표시
                printf(" oo");
            else // 무한대가 아니면 원래 값을 출력
                printf("%3d", D[i][j]);
        }
        printf("\n");
    }
}

int** floyd(int* W[], int* P[], int n)
{
    int i, j, k;
    int** D;
    D = make_array(n);  // 반환할 D 행렬을 만듬

    for (i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            D[i][j] = W[i][j];  // D 행렬 = W 행렬

    for (k = 0; k < n; k++) {
        for (i = 0; i < n; i++)
            for(j = 0; j < n; j++)
                if (D[i][j] > D[i][k] + D[k][j]) {
                    P[i+1][j+1] = k+1; // 경로를 구하기 위한 배열
                    D[i][j] = D[i][k] + D[k][j];
                }
        //printf("\nK = %d :\n", k+1);    // K의 값 출력
        //print_array(D, n);  // K의 변화에 따른 배열 값 출력
    }
    return D;
}

void print_path(int *P[], int q, int r) // P행렬을 이용해서 q부터 r까지의 이동 경로를 출력
{
    if(P[q][r] != 0) {
        print_path(P, q, P[q][r]);
        printf(" v%d -->", P[q][r]);
        print_path(P, P[q][r], r);
    }
}

실행 결과는 대충 이런 분위기이다.

 사실 플로이드 알고리즘보다는 포인터를 이용한 NxN 배열을 다루는 것과 파일에서 배열값을 읽어오는데 좀 더 중점을 두어서 짜보았다. 계속 쓰다 보니 조금은 포인터를 다루는 방법을 알것도 같은 기분도 든다.

참고자료
• 알고리즘(Foundatations of Algorithms Using C++ Pseudocode) - Neapolitan, Naimipour 저 / 도경구 역