[알고리즘] 플로이드 와샬(Floyd Warshall) 알고리즘이란? (C/C++) , C언어 예제

플로이드 와샬 알고리즘

플로이드 와샬(Floyd-Warshall) 알고리즘

플로이드 와샬(Floyd-Warshall) 알고리즘은 모든 노드 쌍 사이의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 그래프의 모든 간선의 가중치를 고려하며, 음수 가중치를 가진 간선도 처리할 수 있지만, 음수 사이클은 처리할 수 없습니다.

이 알고리즘의 핵심 아이디어는 '중간 노드' 개념입니다. 간단히 말해, 노드 i에서 노드 j로 가는 최단 경로는 직접 갈 수 있는 경로와 중간 노드를 거쳐서 가는 경로 중 최소인 것입니다.

플로이드 와샬 알고리즘을 C언어로 구현한 예시를 제공하겠습니다. 이 예시에서는 2차원 배열을 사용하여 그래프를 표현하며, 각 노드는 0부터 시작하는 인덱스로 표현합니다. 

int graph[V][V] 

{ {0, 5, INF, 10},

{INF, 0, 3, INF},

{INF, INF, 0, 1},

{INF, INF, INF, 0} }

라는 그래프를 예시로 그래프의 모든 노드 쌍 사이 최단거리를 출력하는 코드를 C언어로 작성 해 보겠습니다.

 

ㄹ;ㄹ

#include<stdio.h>

#define INF 99999
#define V 4

// 결과를 출력하는 함수
void printSolution(int dist[][V]);

// 플로이드 와샬 알고리즘을 구현하는 함수
void floydWarshall (int graph[][V])
{
    int dist[V][V], i, j, k;

    // 입력 그래프를 바탕으로 dist 배열 초기화
    for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
            dist[i][j] = graph[i][j];

    // 모든 정점을 한번에 한 개씩 중간 정점으로 사용합니다.
    for (k = 0; k < V; k++)
    {
        // 모든 정점을 시작점으로 사용합니다.
        for (i = 0; i < V; i++)
        {
            // 모든 정점을 목적지로 사용합니다.
            for (j = 0; j < V; j++)
            {
                // i에서 j로 가는 기존 거리와 i에서 k를 거쳐 j로 가는 거리를 비교하여 더 작은 값을 선택
                if (dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }

    // 결과 출력
    printSolution(dist);
}

// 최단 거리를 출력하는 함수
void printSolution(int dist[][V])
{
    printf ("다음의 행렬은 각 정점간의 최단 거리를 나타냅니다.\n");
    for (int i = 0; i < V; i++)
    {
        for (int j = 0; j < V; j++)
        {
            if (dist[i][j] == INF)
                printf("%7s", "INF");
            else
                printf ("%7d", dist[i][j]);
        }
        printf("\n");
    }
}

int main()
{
    int graph[V][V] = { {0,   5,  INF, 10},
                        {INF, 0,   3, INF},
                        {INF, INF, 0,   1},
                        {INF, INF, INF, 0}
                      };

    // 플로이드 와샬 알고리즘 실행
    floydWarshall(graph);
    return 0;
}

위의 코드는 주어진 그래프의 최단 경로를 계산하고 출력하는 기본적인 예제입니다. `INF`는 두 노드 사이에 간선이 없음을 나타냅니다. 이 프로그램을 실행하면 그래프의 모든 노드 쌍 사이의 최단 거리를 출력합니다.