/ C

알고리즘 정복하기 with C (1)Floyd's Algorithm II

알고리즘 정복하기 with C (1)Floyd’s Algorithm II

직접 코딩하면서 자료구조 공부하기

개요

자료구조와 알고리즘은 프로그램을 구성하는 가장 핵심적인 요소입니다. 프로그램 개발을 집을 짓는 것에 비유한다면 흙이나 모래, 시멘트, 목재와 같은 자재들이 바로 ‘자료구조’에 해당되고, 이러한 자재들을 이용해서 집을 짓는 것이 ‘알고리즘’에 해당됩니다. 알고리즘은 가장 기본적이고 중요한 부분이기 때문에 복습하는 겸해서 직접 여러가지 알고리즘을 코딩하면서 공부하기로 했습니다.

Floyd’s Algoritm

Floyd’s Algoritm, 플로이드 알고리즘은 가중치를 포함한 그래프의 각 정점에서 다른 모든 정점까지의 최단 거리를 계산하고, 각각의 최단 경로를 구하는 알고리즘입니다. 즉, 모든 정점에서 모든 정점으로의 최단 거리를 구하는 알고리즘으로 Dynamic Programming 으로 구현합니다.

입력값은 가중치를 포함한 방향성 그래프 W와 정점의 수 n / 출력값은 최단 경로의 길이가 포함된 배열 D, 그리고 최단 경로의 정점이 포함된 배열 P입니다.

여기서 D 만을 구하는 알고리즘을 Floyd I, 최단 경로 배열 P를 포함하는 것을 Floyd II 라고 합니다. Floyd II 에서 최단 경로 배열 P를 구하기 위해서 플로이드 알고리즘과 더불어 Path라는 알고리즘을 이용합니다. 이번에는 Floyd II 알고리즘을 구현하도록 하겠습니다.

Floyd’s Algorithm, Path pseudo code

플로이드 알고리즘과 .Path의 pseudo code는 다음과 같습니다.

void floyd(int n, const number W[][], number D[][], index P[][]) {
  index i, j, k;
    for(i=1; i <=n; i++)
      for(j=1; j<=n; j++)
        P[i][j]=0;
    D = W;
    for(k=1; k<=n; k++)
      for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
          if(D[i][k] + D[k][j] < D[i][j]) { //basic operation
            P[i][j] = k; //최단 경로를 저장하여 path함수를 통해 출력
            D[i][j] = D[i][k] + D[k][j];
          }
}

//위에서 만든 P배열로 경로를 출력
void path(index q,r) {
  if(P[q][r] != 0) {
    path(q,P[q][r]);
    cout << "v" << P[q][r];
    path(P[q][r],r);
  }
}

Floyd’s Algorithm II, Path 시간 복잡도

for문을 Basic Operation으로 할 때 3번 중첩되므로 O(n^3)의 시간복잡도를 가지고 있습니다.

Floyd’s Algorithm II 구현

입력데이터

입력데이터

소스코드

#include <stdio.h>

void floyd2(int n, const int W[][6], int D[][6], int P[][6]);
void path(int P[][6], int q, int r);


int main() {
	//가중치 2차원 배열 W 생성
	int W[6][6] = { {0,0,0,0,0,0},
					{0,0,1,6,3,1},
					{0,999,0,5,999,5},
					{0,999,3,0,4,999},
					{0,999,999,5,0,2},
					{0,2,999,999,999,0} };
	//최단거리, 정점 2차원 배열 생성
	int D[6][6];
	int P[6][6];

	//floyd2 및 path 알고리즘 실행
	floyd2(5, W, D, P);

	//계산된 배열 출력
	for (int i = 1; i <= 5; i++)
	{
		for (int j = 1; j <= 5; j++)
		{
			printf("%3d", D[i][j]);
		}
		putchar('\n');
	}

	//정점 4 -> 2 경로 출력
	printf("v4 에서 v2의 최단경로\n");
	printf("v%d", 4);
	path(P, 4, 2);
	printf(" v%d", 2);


	return 0;
}

void floyd2(int n, const int W[][6], int D[][6], int P[][6])
{
	int i, j, k;

	//이동 정점 배열 P 초기화
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= n; j++)
			P[i][j] = 0;
	}

	//가중치 배열로 최단거리 배열 D 초기화
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= n; j++)
			D[i][j] = W[i][j];
	}

	//최단거리 및 정점 배열 계산
	for (k = 1; k <= n; k++)
	{
		for (i = 1; i <= n; i++)
		{
			for (j = 1; j <= n; j++)
			{
				if (D[i][k] + D[k][j] < D[i][j])
				{
					P[i][j] = k;
					D[i][j] = D[i][k] + D[k][j];
				}

			}
		}
	}
}

void path(int P[][6], int q, int r)
{
	if (P[q][r] != 0)
	{
		path(P, q, P[q][r]);
		printf(" v%d", P[q][r]);	//지나는 정점 출력
		path(P, P[q][r], r);
	}
}

결과

플로이드 알고리즘과 최단 경로 출력을 구현했습니다. 결과가 잘 나옵니다.

알고리즘 진행 과정 손계산

알고리즘의 진행과정을 직접 계산하여 결과를 비교해보았습니다. 결과가 동일하게 나옵니다.