Hyokyun Yim bio photo

Hyokyun Yim

Koreatech Computer Science Engineering undergraduate 4 grade.

Facebook Github

최단경로를 구하는 Floyd 알고리즘에 대해 알아보자.

Overview

Floyd Alogorihm

분석/풀이

  • 플로이드 알고리즘 이란? 그래프에서 모든 정점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 그래프의 각 정점과 정점간의 가중치 값을 인접행렬로 표현하고 이 인접행렬을 사용하여 3중 for문으로 구현 한다. 가장 바깥쪽 반복문은 경로사이의 거쳐 가는 정점이고, 두 번째 반복문은 출발하는 정점, 세 번째 반복문은 도착하는 정점이다. 모든 정점 간 경로의 시간 복잡도는O(n^3) 이며 경로를 역으로 추출 하는 알고리즘의 복잡도는 O(n) 을 갖는다.
  • 아래 그래프를 만약 Vi 에서 Vj로의 이음선이 있으면 가중치를 기입하고, 없다면 무한대, 같다면 0으로 표시 한다. 표시한 행렬은 아래 그림과 같다.
  • W 인접한 정점들 사이의 가중치 값들이 저장된 배열 W 즉 인접행렬을 사용하여 최단경로를 구한다. 이때 플로이드 알고리즘을 사용하며 3중 for문을 이용하여 두 정점 간의최단경로 가중치가 저장 된다.

  • 쉬트라센 알고리즘에 따라 다음 7개의 수식으로 곱 C를 표현할 수 있다.

  • 이때 P 행렬을 따로 추가하여 한 정점에서 다른 정점으로 가는 최단 경로상에 있는 중간 정점들 중 가장 큰 인덱스를 저장 할 수 있으며 이를 이용하여 경로상에 있는 즉 지나가는 정점들을 출력할 수 있다.

플로이드 알고리즘 구현 소스코드



#include<stdio.h>
#include<stdlib.h>
#include<vector>//vector를 쓰기위한 라이브러리
#include<math.h>//log, floor 사용
#include<time.h>//clock()
#include<iterator>// back_inserter
using std::vector;
#pragma warning(disable:4996)
#define SIZE 100//행렬 사이즈

// 그래프의 인접행렬 W, 최단경로를 저장할 D, 한 정점과 끝정점 사이에 지나가는 정점중 가장 큰 인덱스가 저장된 P  
// parameter : W, D, P 2차원 벡터 주소
// return : 없음
void floyd(vector<vector<int>> &matrixW, vector<vector<int>> &matrixD, vector<vector<int>> &matrixP)
{
	int i, j, k;
	
	std::copy(matrixW.begin(), matrixW.end(), matrixD.begin());  //배열 카피 D = W
	
	for (i =0; i < (int)matrixW.size(); i++)     //배열의 사이즈만큼 반복문을 돌린다.
	{
		for (j =0; j < (int)matrixW.size(); j++)
		{
			matrixP[i][j] =0;    //0으로 초기화를 시켜줌 
		}
	}
            // 경로사이의 거쳐가는 정점
	for (k =0; k < (int)matrixW.size(); k++)  
	{          // 출반 정점
		for (i =0; i < (int)matrixW.size(); i++)  
		{          // 도착 정점
			for (j =0; j < (int)matrixW.size(); j++)  
			{
                // 만약 원래 가중치 값보다 작을 경우
				if (matrixD[i][k] + matrixD[k][j] < matrixD[i][j]) 
				{
                         //P에 가장 마지막에 지나간 정점 즉 k를 저장(가장 큰 인덱스)
                         //k를 거쳐가는 가중치가 더 작을경우 새로운경로 가중치로 입력 
				          matrixP[i][j] = k;  
				          matrixD[i][j] = matrixD[i][k] + matrixD[k][j];
				}
			}
		}
	}
}





// 바이너리 파일을 읽어와 벡터 2차원 배열에 저장시키는 함수.
// parameter : 읽은 값을 저장시킬 vector 주소 , 파일명, , 행사이즈, 열사이즈 
// return : 없음
void MatrixInit(vector<vector<int>> &matrix, char* fname, int Row, int Col)
{
	FILE *fin;
	fin = fopen(fname, "rb");
	char* arr =newchar[Row*Col*3];
	int idx =2;
	int j =1;
	if (fin ==NULL)
	{
		printf("파일명이 없습니다.\n");
		return;
	}
	if (fread(arr, Row*Col *3, 1, fin) !=1)
	{
		printf("에러");
		exit(1);
	}
	int count =0;
	
	//바이너리 파일을 읽어온 데이터가 배열의 행, 열, 가중치 순으로 총 3만개의 데이터 
	//즉 100x100 배열로 표현할 수 있는 데이터가 존재
	for (int i =0; i <= Row*Col*3-1; i=i+3)
	{
		//fread로 arr에 읽어온 데이터들중 첫번째를 행, 두번째를 열, 그리고 3번째는 가중치이므로 
		//matrix[arr[i]][arr[j]] = arr[idx]; 와 같이 배열에 저장시킨다.
		matrix[arr[i]][arr[j]] = arr[idx];
		j = j +3;
		idx=idx +3;
	}
	fclose(fin);
}

// 시작 정점과 끝 정점 사이의 지나간 정점을 표현해주기위한 재귀함수 
// parameter : 파일 포인터 fout, 벡터 P주소, 시작정점 q, 끝정점 r 
// return : 없음
void OutFilePath(FILE *fout, vector<vector<int>> &P, int q, int r)
{
	if (P[q][r] !=0)
	{
		OutFilePath(fout, P, q, P[q][r]);
		fprintf(fout, "%d->", P[q][r]);
		OutFilePath(fout, P, P[q][r], r);
	}
}









// OutFilePath 함수를 호출하여 두 정점 사이의 지나간 정점들을 저장시키는 함수
// parameter : 파일명 , 벡터 P 주소
// return : 없음
void PathOutput(char*fname, vector<vector<int>> &P)
{
	FILE *fout;
	fout = fopen(fname, "wt");
	for (int i =0; i < (int)P.size(); i++)
	{
		for (int j =0; j < (int)P.size(); j++)
		{
			fprintf(fout, "[시작:%d]->", i);
			OutFilePath(fout, P, i, j);
			fprintf(fout, "[도착:%d]  ", j);
			fprintf(fout, "\n"	);
		}
	}
}

int main()
{
	int Row = SIZE;
	int Col = SIZE;
	char fname1[50], fname2[50];
	int start, end; //시간측정
	
    // ex) vector<vector<int> >  arr(6, vector<int>(5, 0));
	// 설명: vector< vector<int> > 형 벡터 6개(가로 6줄)를 할당 한다는 뜻
	//       vector<int>(5,0) 은 모든 가로줄은 5개짜리 0으로 초기화 된 익명의 
    //       int 형 벡터 배열을 생성해 초기값을 넣는다.
	vector<vector<int>> W1(Row, vector<int>(Col, 0)); // W1[Row][Col] 인 동적 배열
	vector<vector<int>> D1(Row, vector<int>(Col, 0)); // D1[Row][Col] 인 동적 배열
	vector<vector<int>> P1(Row, vector<int>(Col, 0)); // P1[Row][Col] 인 동적 배열
	
	vector<vector<int>> W2(Row, vector<int>(Col, 0)); 
	vector<vector<int>> D2(Row, vector<int>(Col, 0)); 
	vector<vector<int>> P2(Row, vector<int>(Col, 0)); 

	printf("Floyd 알고리즘을 사용하여 최단경로를 탐색합니다.  \n");
	MatrixInit(W1, "denseG.txt", Row, Col);
	MatrixInit(W2, "sparseG.txt", Row, Col);

	printf("deseG 와 sparseG 최단경로 탐색중 ....\n");
	floyd(W1, D1, P1);
	floyd(W2, D2, P2);
	PathOutput("result denseG.txt", P1);
	PathOutput("result sparseG.txt", P2);

	printf("최단경로 탐색이 완료되었습니다.\n결과는 
                            result denseG.txt , result sparseG.txt 로 저장되었습니다. \n\n");

	return 0;
}


코드 해설

  1. floyd 함수 : 인자로 vector 2차원 배열 3개를 입력 받는다. matrixW 는 그래프의 인접행렬이며 matrixD는 최단경로의 길이가 저장되는 배열, matrixP는 두 정점 사이에 있는 정점들 즉 경로상의 정점들 중 가장 큰 인덱스가 저장된다. 먼저 std::copy(matrixW.begin(), matrixW.end(), matrixD.begin()); 배열을 복사한다. 즉 그래프의 인접행렬 W를 D에 복사시키고 이를 활용해 최단경로를 구한다. 그리고 경로상의 정점 중 최대 인덱스를 저장할 P를 0으로 초기화 시킨다. 그런 후 3중 for문을 사용하여 가장 바깥 k가 경로사이의 거쳐가는 정점들을 말하며 두 번째 for문 I는 출발점 3번째 for문 j는 도착 정점을 말한다. matrixD[i][k] + matrixD[k][j] < matrixD[i][j] 정점 k를 지나간 경로의 길이가 원래 저장된 길이 보다 작다면 이 값으로 교체한다. 그리고 P에는 이 정점 k의 값을 저장한다. 최종적으로 정점간의 최단경로의 길이가 가 D에 저장되고 P에는 경로 상에서 지나간 정점 중 가장 큰 인덱스의 정점이 저장된다.

  2. MatrixInit 함수 : 인자로 파일에서 읽은 값을 저장시킬 vector 2차원 배열, 불러올 파일명, 행사이즈, 열사이즈를 입력받는다. 함수 내부에 FILE 포인터 변수 fin을 선언하고 바이너리 파일을 읽을 수 있도록 rb로 파일을 오픈한다. 읽어온 값들을 1차적으로 저장 시키기 위해 동적배열 arr을 만들어 준 후 fread(arr, Row * Col *3 , 1 , fin) 함수를 호출한다. 즉 30000개의 데이터를 1바이트씩 값을 읽어서 arr 배열에 저장 시킨다. 1차적으로 arr 배열에 저장한 데이터들을 보면 행, 열, 가중치, 행, 열, 가중치, …. 순으로 3만개 즉 그래프를 100x100 인접행렬로 표현할 수 있는 데이터가 저장되어 있다. 이 데이터를 행렬로 다시 표현하기 위해 matrix[arr[i]][arr[j]] = arr[idx]; 데이터의 첫 번째를 행으로 두 번째를 열로 3번째를 가중치로 보고 다시 2차원 벡터 배열에 저장시켜 그래프 인접행렬을 만든다.

  3. OutFilePath 함수 : 인자로 vector 2차원 배열 1개, 시작 인덱스 q, 끝 인덱스 r을 받는다. 이 함수는 출발 정점과 끝 정점의 최단경로상의 지나가는 정점들을 파일로 저장해주는 함수의 기능을 갖추고 있다. P[q][r] 이 만약 0 이 아닐 경우 P[q][r] 현재 최대 인덱스로 저장된 값에서 q -> P[q][r] 과 P[q][r] -> r P[q][r]을 중심으로 2부분으로 나누어 가면서 재귀적으로 구현한다. 더 이상 정점이 없을 경우 파일에 저장시킨다.

  4. PathOutput 함수 : 인자로 파일명과 , vector 2차원 배열 1개를 입력 받는다. 파일 포인터를 선언하고 파일명에 맞게 쓰기로 열고, 2중 for문으로 시작 정점과 끝 정점의 경로를 지나가는 정점들을 모두 저장하기 위해 OutFilePath 함수를 호출하여 [시작정점] -> k->k ……-> [끝 정점] 형식으로 저장한다.

  5. main 함수 : 2차원 vector 배열 6개를 만든다. 이 배열들은 각각 3개씩 denseG , sparseG 그래프의 인접행렬과 , 최단경로 길이, 경로상의 정점들 에 대한 값들이 저장 된다. 위에서 설명한 함수들을 호출하여 최단경로를 구하고 결과를 저장한다.

코드 실행 결과