다익스트라 알고리즘 C언어로 구현

다익스트라 알고리즘 Dijkstra algorithm

• 하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리를 구하는 방식
• 첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며, 최단 거리를 갱신하는 기법
• 다익스트라 알고리즘은 너비우선탐색(BFS)와 유사
  • 첫 정점부터 각 노드간의 거리를 저장하는 배열을 만든 후, 첫 정점의 인접 노드 간의 거리부터 먼저 계산하면서, 첫 정점부터 해당 노드간의 가장 짧은 거리를 해당 배열에 업데이트

    다익스트라 알고리즘의 다양한 변형 로직이 있지만, 가장 개선된 우선순위 큐를 사용하는 방식을 소개

구현 방식

• 우선순위 큐는 MinHeap 방식을 활용해서, 현재 가장 짧은 거리를 가진 노드 정보를 먼저 꺼내게 됨
  1) 첫 정점을 기준으로 배열을 선언하여 첫 정점에서 각 정점까지의 거리를 저장

  • 초기에는 첫 정점의 거리는 0, 나머지는 무한대로 저장함 (inf 라고 표현함)
  • 우선순위 큐에 (첫 정점, 거리 0) 만 먼저 넣음

  2) 우선순위 큐에서 노드를 꺼냄

  • 처음에는 첫 정점만 저장되어 있으므로, 첫 정점이 꺼내짐
  • 첫 정점에 인접한 노드들 각각에 대해, 첫 정점에서 각 노드로 가는 거리와 현재 배열에 저장되어 있는 첫 정점에서 각 정점까지의 거리를 비교한다.
  • 배열에 저장되어 있는 거리보다, 첫 정점에서 해당 노드로 가는 거리가 더 짧을 경우, 배열에 해당 노드의 거리를 업데이트한다.
  • 배열에 해당 노드의 거리가 업데이트된 경우, 우선순위 큐에 넣는다.
    • 결과적으로 너비 우선 탐색 방식과 유사하게, 첫 정점에 인접한 노드들을 순차적으로 방문하게 됨
    • 만약 배열에 기록된 현재까지 발견된 가장 짧은 거리보다, 더 긴 거리(루트)를 가진 (노드, 거리)의 경우에는 해당 노드와 인접한 노드간의 거리 계산을 하지 않음

  3) 2번의 과정을 우선순위 큐에 꺼낼 노드가 없을 때까지 반복한다.

void    dijkstra(LinkedGraph *graph, int from)
{
    int             INF = 9999999;
    int             dp[graph->maxVertexCount];
    Heap        *heap = createHeap(graph->maxVertexCount);
    HeapNode    buf = {0, };
    HeapNode    insertNode = {0, };
    ListNode    *temp;

    for(int i = graph->maxVertexCount - 1; i >= 0; i--)
        dp[i] = INF; // 배열의 모든 값은 무한대로 설정한다.
    dp[from] = 0; // 시작점은 0으로 한다.
    insertMinHeapNode(heap, buf); // 시작점을 min heap 에 넣어준다.
    while (getMinHeapLength(heap) != 0)
    {
        buf = popMinHeapNode(heap);
        temp = graph->ppAdjEdge[buf.idx]->headerNode.pLink;
        while(temp)
        {
            if (dp[temp->data.vertexID] > temp->data.weight + buf.key)
            // 만약 배열에 저장 된 값보다 작다면
            {
                dp[temp->data.vertexID] = temp->data.weight + buf.key;
                insertNode.key = dp[temp->data.vertexID];
                insertNode.idx = temp->data.vertexID;
                insertMinHeapNode(heap, insertNode);
                // 업데이트 하고, 힙에 넣어주며 더 짧은 거리가 있는지 확인한다.
            }
            temp = temp->pLink;
        }
    }
    for (int i = 0; i < 6; i++)
        printf("%d ", dp[i]);
}