플로이드 알고리즘 C언어로 구현

플로이드 알고리즘 Floyd algorithm

• 모든 지점에서 모든 지점으로의 최단 경로를 모두 구하는 경우
• 꼭짓점 k를 두고, k를 경유할 경우를 원래의 값과 비교하여 더 짧다면 업데이트 한다.
  • (i,j) > (i,k) + (k,j) 와 같은 꼴이다.
• 다이나믹 프로그래밍 기술에 의거한다.
• 구현이 쉽고 간단하지만 O(n^3) 시간복잡도가 높다.

구현

int    INF = 99999999;

int **arr_init(LinkedGraph *graph)
{
    int **arr = calloc(graph->currentVertexCount, sizeof(int *));
    ListNode *temp;
    for(int i = 0; i < graph->currentVertexCount; i++)
        arr[i] = calloc(graph->currentVertexCount, sizeof(int));
    for (int i = 0; i < graph->currentVertexCount; i++)
    {
        for(int j = 0; j < graph->currentVertexCount; j++)
        {
            arr[i][j] = INF;
            if (i == j)
                arr[i][j] = 0;
        }
    }
    for (int i = 0; i < graph->currentVertexCount; i++)
    {
        temp = graph->ppAdjEdge[i]->headerNode.pLink;
        while(temp)
        {
            arr[i][temp->data.vertexID] = temp->data.weight;
            temp = temp->pLink;
        }
    }
    return arr;
}

void    display(int **arr, int length)
{
    for(int i = 0; i < length; i++)
    {
        for(int j = 0; j < length; j++)
        {
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }
}

void    floyd(LinkedGraph *graph)
{
    int    **arr = arr_init(graph); // 결과 그래프를 초기화한다.

    for (int k = 0; k < graph->maxVertexCount; k++) // 꼭짓점 K
    {
        for(int j = 0; j < graph->maxVertexCount; j++)
        {
            for(int i = 0; i < graph->maxVertexCount; i++)        
            {
                if (arr[i][j] > arr[i][k] + arr[k][j]) 
                // (i,j) 가 (i,k) + (k,j)보다 크다면 업데이트한다.
                    arr[i][j] = arr[i][k] + arr[k][j];
            }
        }
    }
    display(arr, graph->maxVertexCount);
}