Dijkstra’s Algorithm

Prim 알고리즘에 이어서 Prim과 굉장히 유사한 Dijkstra 알고리즘을 소개하려 한다.
Dijkstra 알고리즘은 Shortest Path를 찾는 알고리즘이다.

앞서 소개했던 Prim 알고리즘과의 차이점은 다음과 같다.

  1. 정점을 하나 선택할 경우, 선택된 정점까지 오는 간선의 가중치를 선택된 정점과 연결된 모든 간선에 더해준다.
    *이것을 간선 경감(Edge Relaxation)이라고 한다.
  2. 이렇게 더한 상태에서 최소 힙을 통해서 최소 간선을 뽑아낸다. 앞의 Prim 알고리즘과 사용된 자료구조는 완벽하게 동일하다. Prim 알고리즘에서 소개했던 인접 리스트를 그대로 사용하며, 최소 힙 또한 그대로 사용한다.

Dijkstra 알고리즘의 진행은 다음과 같다.

  1. 인풋 그래프는 Prim에서 사용했던 그것과 동일한 인풋을 사용한다.
  2. 1번 정점부터 알고리즘을 시작하게 되어있다.
    따라서, 1번 정점을 선택한다.
    * 이것을 위해서 힙을 초기화할 때, 초기값으로 (1, 1, 0)=(start_v, end_v, w)를 넣고 시작한다.
    최소 힙에 의해서 2번 정점이 선택된다.
    2번 정점이 선택되고나면, 2번 정점과 연결된 2->4 간선의 가중치와 2->3 간선의 가중치에 대해서 각각 1->2 간선의 가중치였던 1을 더해준다.
  3. 이제 다시 힙에서 최소값을 비교한다.
    힙에는 선택된 정점들과 연결된 간선들만이 추가되게 되므로, 위의 2번까지 진행된 상태에서 힙 속에서는,
    1->3, 2->3, 2->4 이렇게 3개의 간선이 들어있게 된다.
    당연히 최소 힙의 정의에 따라 힙의 루트에는 1->3 의 간선이 들어있게 된다.
    3번 정점을 선택하고 나서 2번과 같은 과정을 반복한다.
  4. 이제 힙 속에는, 2->3, 2->4, 3->4, 3->5 이렇게 4개의 간선이 들어있게 된다.
    여기에서 최소힙을 구성하고 루트노드를 삭제하게 되면, 2->3의 간선이 선택될 것이다.
    하지만 이 경우에는 이미 3번 정점이 선택되어 있으므로, 사이클이 형성되게 된다.
    그러면, 최단경로트리가 되지 않으므로, 이 간선을 버려야 한다.
    이 부분은 코드에서 near 배열의 값으로 해결하게 된다.
    *Prim 알고리즘에서도 이와 완전히 같은 방법을 사용해서 사이클이 생성되는 것을 방지하였다.
    사이클이 생기는 간선을 제외한 최소값을 가지는 간선에는, 2->4 와 3->4 가 각각 가중치 7의 값을 가지고 있다.
    힙이 생성되는 시기에 따라서 간선이 선택되게 되는데, 어떠한 것을 선택하게 되더라도 결과에는 변합이 없다.
    우리는 3->4 간선을 선택한다.
  5. 이제 힙 속에는, 2->4, 3->5, 4->5 이렇게 3개의 간선이 들어있게 된다.
    4번과 마찬가지로 2->4 의 간선이 최소값의 가중치를 가지지만 사이클을 형성하게 되므로, 선택하지 않는다.
    그러므로, 다음 최소값인 3->5 의 간선을 선택하게 된다.
  6. 이제 5개의 모든 정점이 선택되었으므로, 알고리즘을 종료한다.
    최종적인 그래프는 다음과 같다.
     Prim 알고리즘을 통해서 알아본 최소 비용의 총 합이 13이었는데, Dijkstra를 통해서 알아본 최소 비용의 총합 역시 13이다.
    위의 그림에서 8과 7은 각각 3을 거쳐온 가중치가 되므로, 최소 비용을 계산할 때에는 제외시켜 주어야 한다.

이러한 로직을 가지는 Dijkstra 알고리즘을 코드로 구현하면 다음과 같다.

#include <stdio.h>
#include <stdlib.h>

#pragma warning(disable:4996)
#define MAX_FILE_NAME 50
#define MAX_HEAP_SIZE 4096
#define TRUE          1
#define FALSE         0
#define NOT_SELECTED -1

typedef struct _LIST {
    int startVertex;
    int endVertex;
    int weight;
    struct _LIST *next;
} LIST;

typedef struct _HEAP_NODE {
    int startVertex;
    int endVertex;
    int w;
} HEAP_NODE;

typedef struct _HEAP {
    int size;
    struct _HEAP_NODE *heap;
} HEAP;


void list_Create(LIST *p, int start, int end, int w);
void heap_Initialize(HEAP *h);
void heap_Insert(HEAP *h, LIST *l);
void heap_Build(HEAP *h);
void heap_SiftDown(HEAP *h, int i);
void heap_Swap(HEAP_NODE *dst, HEAP_NODE *src);
int heap_Delete(HEAP *h);
void heap_AddWeight(HEAP *h, int weight, int key);


int main() {
    FILE *fp_in;
    char input[MAX_FILE_NAME];
    LIST *list;
    HEAP h;
    int numberOfVertices, numberOfEdges;
    int i, counter;
    int tmp_start, tmp_end, tmp_w;
    int x, y, z;
    int *near, *dist;

    printf("Enter the FILE Name or Path => ");
    scanf("%s", input);

    fp_in = fopen(input, "r");
    if (fp_in == NULL) {
        fprintf(stderr, "FILE <%s> open error.\n", input);
        return -1;
    }

    fscanf(fp_in, "%d %d", &numberOfVertices, &numberOfEdges);

    list = (LIST *) malloc(sizeof(LIST) * (numberOfVertices + 1));
    if (list == NULL) {
        fprintf(stderr, "Memory allocation error: *list\n");
        return -1;
    }

    for (i = 1; i <= numberOfVertices; i++) {
        list[i].next = NULL;
        list[i].startVertex = i;
        list[i].endVertex = -1;
        list[i].weight = -1;
    }

    for (i = 1; i <= numberOfEdges; i++) {
        fscanf(fp_in, "%d %d %d", &x, &y, &z);
        list_Create(&list[x], x, y, z);
        list_Create(&list[y], y, x, z);
    }

    near = (int *) malloc(sizeof(int) * (numberOfVertices + 1));
    if (near == NULL) {
        fprintf(stderr, "Memory allocation error: *n\n");
        return -1;
    }
    dist = (int *) malloc(sizeof(int) * (numberOfVertices + 1));
    if (dist == NULL) {
        fprintf(stderr, "Memory allocation error: *d\n");
        return -1;
    }

    for (i = 1; i <= numberOfVertices; i++) {
        near[i] = NOT_SELECTED;
        dist[i] = 0;
    }

    heap_Initialize(&h);

    counter = 0;
    while (TRUE) {
        if (counter == numberOfVertices) {
            break;
        }

        while (TRUE) {
            tmp_start = h.heap[1].startVertex;
            tmp_w = h.heap[1].w;
            tmp_end = heap_Delete(&h);
            if (near[tmp_end] == NOT_SELECTED) {
                heap_Insert(&h, &list[tmp_end]);
                near[tmp_end] = tmp_start;
                dist[tmp_end] = tmp_w;
                heap_AddWeight(&h, tmp_w, tmp_end);
                counter++;
                break;
            }
        }
    }

    printf("\n=====================================================\n");
    printf("Index   : ");
    for (i = 1; i <= numberOfVertices; i++) {
        printf("%3d ", i);
    }
    printf("\nNearest : ");
    for (i = 1; i <= numberOfVertices; i++) {
        printf("%3d ", near[i]);
    }
    printf("\nDistance: ");
    for (i = 1; i <= numberOfVertices; i++) {
        printf("%3d ", dist[i]);
    }
    printf("\n=====================================================\n");

    fclose(fp_in);
    free(list);
    free(dist);
    free(near);
    free(h.heap);

    return 0;
}

void list_Create(LIST *p, int start, int end, int w) {
    LIST *tmp, *list;

    list = p;
    tmp = (LIST *) malloc(sizeof(LIST));
    if (tmp == NULL) {
        fprintf(stderr, "Memory allocation error: list_Create()\n");
        return;
    }

    tmp->next = NULL;
    tmp->startVertex = start;
    tmp->endVertex = end;
    tmp->weight = w;

    while (TRUE) {
        if (list->next == NULL) {
            list->next = tmp;
            break;
        } else {
            list = list->next;
        }
    }
}

void heap_Initialize(HEAP *h) {
    h->heap = (HEAP_NODE *) malloc(sizeof(HEAP_NODE) * MAX_HEAP_SIZE);
    if (h->heap == NULL) {
        fprintf(stderr, "Memory allocation error: heap_Initialize()\n");
        return;
    }

    h->size = 1;
    h->heap[1].startVertex = 1;
    h->heap[1].endVertex = 1;
    h->heap[1].w = 0;
}

void heap_Insert(HEAP *h, LIST *l) {
    LIST *list = l;

    if (list->next == NULL)
        return;

    while (list != NULL) {
        if (list->weight != -1) {
            h->size++;
            h->heap[h->size].startVertex = list->startVertex;
            h->heap[h->size].endVertex = list->endVertex;
            h->heap[h->size].w = list->weight;
            heap_Build(h);

            list = list->next;
        } else
            list = list->next;
    }
}

void heap_Swap(HEAP_NODE *dst, HEAP_NODE *src) {
    int tmp_start = dst->startVertex;
    int tmp_end = dst->endVertex;
    int tmp_w = dst->w;

    dst->startVertex = src->startVertex;
    dst->endVertex = src->endVertex;
    dst->w = src->w;
    src->startVertex = tmp_start;
    src->endVertex = tmp_end;
    src->w = tmp_w;
}

int heap_Delete(HEAP *h) {
    int min;

    min = h->heap[1].endVertex;
    heap_Swap(&h->heap[1], &h->heap[h->size]);
    h->size--;
    heap_Build(h);

    return min;
}

void heap_SiftDown(HEAP *h, int i) {
    int largerChild;
    HEAP_NODE siftKey;
    int parent = i;
    int found = FALSE;

    siftKey = h->heap[i];
    while ((2 * parent <= h->size) && !found) {
        if ((2 * parent < h->size) && (h->heap[2 * parent].w > h->heap[2 * parent + 1].w)) {
            largerChild = 2 * parent + 1;
        } else {
            largerChild = 2 * parent;
        }

        if (siftKey.w > h->heap[largerChild].w) {
            h->heap[parent] = h->heap[largerChild];
            parent = largerChild;
        } else
            found = TRUE;
    }

    h->heap[parent] = siftKey;
}

void heap_Build(HEAP *h) {
    int i;

    for (i = h->size / 2; i >= 1; i--) {
        heap_SiftDown(h, i);
    }
}

void heap_AddWeight(HEAP *h, int weight, int key) {
    int i;

    for (i = 1; i <= h->size; i++) {
        if (h->heap[i].startVertex == key)
            h->heap[i].w += weight;
    }

    heap_Build(h);
}

코드는 앞서 소개한 Prim 알고리즘의 코드와 거의 흡사하므로, 차이점에 대해서만 보자.

Prim의 코드와 변경된 부분은 코드라인 113번이다.
Dijkstra의 작동 원리를 위해서, 선택된 정점에 대해서 각각 연결된 간선에 가중치를 더해주는 부분이다.
그 부분에 대한 코드는 다음과 같다.

void heap_AddWeight(HEAP *h, int weight, int key) {
    int i;

    for (i = 1; i <= h->size; i++) {
        if (h->heap[i].startVertex == key)
            h->heap[i].w += weight;
    }

    heap_Build(h);
}

힙 전체에 대해서 파라미터 key는 각각 출발 정점이 key 인 노드들을 의미하게 된다.
즉, 힙 전체에 대해서 2번 정점이 선택된 경우, 2번 정점에서 출발하는 모든 간선들에 대해서 각각 그들의 가중치에다가 weight만큼을 더해주는 함수이다.
이렇게 가중치를 더해주고 나서는 반드시 새롭게 heap_Build() 함수를 호출해주어야 한다.
*가중치를 더함으로써 루트노드가 변경될 수 있기 때문이다.
게시글에서 소개했던 테스트 케이스에 대해서 직접 프로그램을 구현한 결과는 다음과 같다.
 Nearest 로 출력된 부분은 각각의 정점에 대해서 어느 정점과 연결되었는지를 표현한 것이다.
위의 6번 그림과 같은 결과를 볼 수 있다.

댓글 남기기