[알고리즘] 플로이드 알고리즘, Floyd's Algorithms | 설계 및 분석 , 구현코드

플로이드 알고리즘이란?

  한 도시에서 다른 도시로 가는 직항로가 없는 경우 가장 빨리 갈 수 있는 항로를 찾는 shortest path 문제들 중 하나이다. 플로이드 알고리즘은 가중치 포함 그래프의 각 정점에서 다른 모든 정점까지의 최단 거리를 구한다.

 

  플로이드 알고리즘이 shortest path 문제들 중 한 유형이므로, 플로이드 알고리즘을 살펴보기 전에 shortest path의 특징을 먼저 알아볼 필요가 있다. 

 

<shortest path 문제에서 사용하는 자료구조>

① W : 그래프의 인접행렬  

     W[i][j] = 이음선의 가중치 (v_i에서 v_j로의 이음선이 있는 경우)

                  =  ∞                         (v_i에서 v_j로의 이음선이 없는 경우)

                  =   0                          ( i = j인 경우 )

 

그래프를 컴퓨터가 알아볼 수 있도록 배열(인접행렬)로 변환

 

② D^(k) : 각 정점들 사이의 최단거리 (floyd 알고리즘에서 고안)

     k : 중간에 거쳐갈 수 있는 정점의 수

     D^(k)[i][j] = {v₁, v₂, ... , v_k}의 정점들 만을 통해서 v_i에서 v_j로 가는 최단경로의 길이

 

알고리즘 설계전략

① 재귀 관계식 정립

  D^(k)[i][j] 값을 결정하는 데에 2가지 경우가 있다.

V를 지나는 경우와 V를 지나지 않는 경우인데, 이 두 가지 경우 중 어떤 경우의 경로를 비교하여 더 짧은 값을 선택해야하고, 이 관계식을 아래와 같이 표현한다.

 

 

② bottom-up 방식으로 해결

  k - 1(이전 항)까지의 최단 경로를 이용하여 k(다음 항) 값을 결정

 

알고리즘 수도코드

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);
  }
}

 

알고리즘 성능분석

basic operation : D[i][k] +  D[k][j] < D[i][j],  새로운 정점 k를 추가하여 k를 거치는 것이 더 빠른지, 아니면 k를 추가하지 않는게 더 빠른지 검사하는 부분

 

floyd's 알고리즘은 every-case이다. 따라서 저 basic operation을 바탕으로 연산 횟수를 계산해보면 basic operation이 총 3중 for문 속에 들어있으므로 n x n x n = n³이다.

∴T(n) = n x n x n ∈ Θ(n³)

 

구현코드

#include <stdio.h>

#define N 5 // 정점 수
#define INF 1000

void floyd2(int n, const int(*W)[N + 1], int(*D)[N + 1], int(*P)[N + 1]);
void path(int(*P)[N+1], int q, int r);

int main(void)
{
	int W[N+1][N+1] = { {0,0,0,0,0,0},  //입력 값
						{0,0,1,INF,1,5},
						{0,9,0,3,2,INF},
						{0,INF,INF,0,4,INF},
						{0,INF,INF,2,0,3},
						{0,3,INF,INF,INF,0},
	};

	int D[N+1][N+1];
	int P[N+1][N+1];

	floyd2(N, W, D, P);

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			printf("%3d", D[i][j]);
		}
		printf("\n");
	}

	int start, end;
	start = 2;
	end = 5;
	printf(" v%d -> ", start);
	path(P, start, end);
	printf("v%d\n", end);

	return 0;
}

void floyd2(int n, const int(*W)[N+1], int(*D)[N+1], int(*P)[N+1])
{
	int i, j, k;

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

	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)[N+1],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);
	}
}

 

입력 값

 

실행 결과

v₂ -> v₄ -> v₅