�ݺ�ߣ

B2조 자료구조
5. 최단거리 찾기

조장 : 20113324 최수영
조원 : 20083430 강승우
20093532 최완철
20113277 김성진
20113272 김남희

과제수행일지
소속 조원
B2 조장 : 최수영 자료조사 : 강승우, 최수영, 김남희 코딩 : 최완철, 김성진
과제수행기간 5.31~6.7
I. 계획의 작성
연구제목 최단거리 찾기

연구배경 어떤 알고리즘을 사용해서든 최단거리를 찾는다.

http://internet512.chonbuk.ac.kr/datastructure/graph/graph2_5_16.htm
참고자료 참고 URL
http://forum.falinux.com/zbxe/?document_srl=535875

II. 계획의 실행
첫째 날 2012년 5월 31일 목요일
오늘의 작업 프로젝트에 대한 이해와 업무 분담

각자 역할을 분담하고, c로 최단거리 찾는 것을 구현하는 것에 앞서, 팀원들끼리 예시를 들어
토의 내용
가며 문제를 풀어보았다.

과제준비에서 이번 프로젝트를 어떤 식으로 푸는지 이해하기가 좀 어려웠고, 첫 회의라 자료가 부족하여 토
느낀 점 의가 원활하게 진행되지 않은 부분이 아쉬웠다.

둘째 날 2012년 6월 5일 화요일

오늘의 작업 각자 조사해온 것들을 종합하여 어떤 방향으로 프로젝트를 완성해나갈지 토의하였다.

플로이드-와셜 알고리즘(Floyd-Warshall Algorithm)
그래프에서 모든 정점간의 최단거리를 구하는 알고리즘이다. 음수 간선도 사이클만 없다면 잘 처리된
다. 제일 바깥쪽 반복문은 거쳐 가는 정점이고, 두 번째 반복문은 출발하는 정점, 세 번째 반복문은
도착하는 정점이다.

동작원리 자체는 매우 간단하다. A에서 B로 갈 수 있는 경로가
토의 내용 있고, 또한 B에서 C로 갈 수 있는 경로가 있다고 한다면 결국 A
에서 C로 갈 수 있는 경로가 있다고 할 수 있다. 만약 A에서 C
로 '직접' 갈 수 있는 경로가 원래 존재했는데 직접 갈 때의 비용
이 B를 거쳐 C로 가는 것보다 많이 든다고 하자. 그러면 플로이
드 알고리즘에서는 A에서 C로 가는 것을 폐기하고 A에서 B를
거쳐 C로 가는 '최단거리' 로 업데이트를 하게 된다.

이 그래프에 대하여 플로이드 알고리즘을 적용해본다면

D 1 단계 - 어떠한 경로도 거치지 않을 때
A B C 항상 자신에서 자신으로 가는 값은 0이 된다.
-1
A 0 4 11 A에서 C로 갈 때 11이라는 것과 C에서 B로
B 6 0 2 갈 때 무한대라는 것을 주목하라.
C 3 ∞ 0

2 단계 - 경로 하나를 거칠 수 있을 때 (예제에
서는 정점이 3개밖에 안되므로 2단계가 사실상
마지막이 된다.)

D For 문을 돌면서 하나씩 검사해 나간다. A에서
A B C
-2 A로 가는 방법은 물론 0이며 A에서 B로 가는
A 0 4 7
방법또한 변함없이 한가지 뿐이다. A에서 C로
B 6 0 2
C 3 ∞ 0 갈 때 두 가지 방법이 생기는데 첫째, A >C 의
방법으로 값은 11이다. 둘째, A에서 B를 거쳐
C로 가는 방법으로 값은 3 + 4 = 7이다. 따라
서 왼쪽 표에서 11을 7로 바꾼다.

For 문을 돌면서 계속 검사해 나간다. B에서 A
로 갈 때 두 가지 방법이 생기는데 첫째, B >A

D 의 방법으로 값은 6이다. 둘째, B에서 C를 거쳐
A B C A로 가는 방법으로 값은 2 + 3 = 5이다. 따라
-2
A 0 4 7 서 왼쪽 표에서 6을 5로 바꾼다. B에서 B로는
B 5 0 2 0이며 B에서 C로 가는데는 2가지 방법이 생겼
C 3 ∞ 0 지만 또다른 방법은 6 + 11 = 17이나 되므로
현재의 것이 최적이기에 바꾸지 않는다.

C에서 A로 가는 방법은 변함없이 한가지 뿐
D 이며, 드디어 C에서 B로 갈 수 있게 되었다.
A B C
-2 C >A >B 의 방법을 통해 3 + 4 = 7의 값으
A 0 4 7
로 B에 도달할 수 있다. 따라서 왼쪽 표의 무
B 5 0 2
C 3 7 0 한대를 7로 수정한다.C에서 C로 가는 방법은
물론 0이다.

D
A B C
-2
A 0 4 7 완성된 표이다.
B 5 0 2
C 3 7 0

- 플로이드-와셜 알고리즘(Floyd-Warshall Algorithm)
최단거리 찾기 알고리즘으로 만들어진 알고리즘이다.

다익스트라의 알고리즘은 시작정점 하나에 대하여 다른 모든 정점까지의 최단거리를 구하
는데 사용된다. 각각의 모든 정점에서 다른 모든 정점까지의 최단 거리를 구하고자 한다면,
다익스트라의 알고리즘을 n번 수행함으로서 얻을 수 있다.

프로이드 알고리즘은 보다 효율성을 위해 제안되었다.
주어진 그래프를 구성하는 정점 사이의 간선 E(i, j)에 두 정점 사이의 거리를 나타내는 가
중치를 부여한다.

이러한 가중치는 C(i, j) 로서 표현된다. 만일 n 개의 정점으로 이루어진 그래프를 고려한다
면, 그래프를 나타내는 n*n 의 행렬 adj_matrix[][] 와 거리를 나타내는 n*n 의 행렬
dist[][] 를 구성한다.

shortest_floyd(int adj_matrix[][]) {

dist[SIZE][SIZE];

dist[][] = adj_matrix[][] 로 초기화

for(k = 0; k < n; k++)

for(i = 0; i < n; i++)

for(j = 0; j < n; j++)

dist[i][j] = Min(dist[i][j], dist[i][k] + dist[k][j]);

return(dist);

}

플로이드-와셜 알고리즘이라는 우리가 완성해야 하는 프로젝트에 딱
느낀점
적합한 알고리즘을 알아냈다는 점이 뿌듯하였다.

결과

#include <stdio.h>
#include <stdlib.h>
#define M 999999

int **arr;
int **arr2;
int **arr3;
int **path;
int n=0;
char alpha[20];

int floyd()
{
int i,j,k;

for(k=1;k<n;k++)
{
for(i=1;i<n;i++)
{
for(j=1;j<n;j++)
{
최종프로그램
if(arr[i][k]+arr[k][j]<arr[i][j])
소스
{
arr[i][j]=arr[i][k]+arr[k][j];
path[i][j] = k;
}
}
}
}

arr2=(int **)malloc(sizeof(int)*n);
for(i=0;i<n;i++)
arr2[i]=(int*)malloc(sizeof(int)*n);

for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
arr2[i][j]=arr[i][j];
}

arr3=(int **)malloc(sizeof(int)*n);
for(i=0;i<n;i++)
arr3[i]=(int*)malloc(sizeof(int)*n);

for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
arr3[i][j]=arr[i][j];
}
}

int print()
{
int i,j;

for(i=1;i<n;i++)
{
for(j=1;j<n;j++)
printf("%d ",arr[i][j]);
printf("n");
}
}

int scan()
{
FILE *fp = fopen("test.txt","rt");
char str[5],ch;
int c1,c2,weight,i,j;

fgets(str,sizeof(str),fp);

n = atoi(str)+1;

arr=(int **)malloc(sizeof(int)*n);
for(i=0;i<n;i++)
arr[i]=(int*)malloc(sizeof(int)*n);

path=(int **)malloc(sizeof(int)*n);
for(i=0;i<n;i++)
path[i]=(int*)malloc(sizeof(int)*n);

for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
path[i][j]=0;
}

for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j)
arr[i][j]=0;
else
arr[i][j]=M;
}
}

while(1)
{
ch = fgetc(fp);
c1 = alphacheck(ch);
ch = fgetc(fp);
c2 = alphacheck(ch);

if(fgets(str,sizeof(str),fp)!=NULL)
weight=atoi(str);
else
break
arr[c1][c2]=weight;
arr[c2][c1]=weight;
}

}

int alphacheck(char ch)
{
int cnt=0,i;

for(i=0;i<20;i++)
{
if(ch==alpha[i])
{
cnt = 1;
break
}
}

if(cnt==0)
{
for(i=0;i<20;i++)

{
if(alpha[i]==NULL)
{
alpha[i]=ch;
break
}
}
}
return i+1;
}

int pathsearch(int a,int b)
{
if(path[a][b])
return path[a][b];
else
return 0;
}

int shotestpath3()
{
int min=M,i,j,k,mins[3],cnt=0,i1,j1;
char shot[3][20];

for(k=0;k<3;k++)
{
min = M;

for(i=1;i<n;i++)
{
for(j=1;j<n;j++)
{
if(arr2[i][j]!=0)
{
if(arr2[i][j]<min)
{
min = arr2[i][j];
i1 = i;
j1 = j;
}
}
}
}

mins[k]= min;

arr2[i1][j1] = 0;
arr2[j1][i1] = 0;
}

for(k=0;k<3;k++)
{
printf("%d - Weight : %d , ShortestPath : ",k+1,mins[k]);
for(i=1;i<n;i++)
{
for(j=1;j<n;j++)
{
if(mins[k]==arr[i][j])
{
arr[i][j]=0;
arr[j][i]=0;
cnt = 0;
printf("%c->",alpha[i-1]);

min = pathsearch(i,j);
while(min!=0)
{
shot[k][cnt] = alpha[min-1];
min = pathsearch(i,min);
cnt++;
}
i=n;
break
}
}
}

for(i=cnt-1;i>=0;i--)
printf("%c->",shot[k][i]);
printf("%cn",alpha[j-1]);

}
}

int shotestpath()
{
int i,j,k,min,sum=0,i1;

for(k=0;k<3;k++)
{
min = M;

for(i=1;i<n;i++)
{
sum = 0;
for(j=1;j<n;j++)
sum += arr3[i][j];
if(min>sum && sum!=0)
{
min = sum;
i1 = i;
}
}

for(i=0;i<n;i++)
arr3[i1][i] = 0;

printf("%d - Weight : %d , ShotestPath : %cn",k+1,min,alpha[i1-1]);
}
}

/*
4
AB 2
AC 6
AD 7
BD 5
CD 3
BC 4
*/

int main(void)
{

scan();

floyd();

//shotestpath();

shotestpath3();

return 0;
}

플로이드-와셜 알고리즘이라는 것이 생각보다 꽤 어려워서 이해
과제를 마치면서 하는데 다들 애먹지 않았나 싶다. 하지만 이 알고리즘이 우리가
느낀 점 해결해야 하는 프로젝트에 적합한 알고리즘이라는 점에서 상당히
좋았다. 그리고 우리조 같은 경우에는 출력 결과를 어떻게 뽑아
내야 할지 상당히 고민을 많이 하였다. path 하나하나의 길이를
비교하여 가장 짧은 3개를 뽑아낼지, 모든 노드를 다 지나는 가
장 짧은 최단거리를 찾아낼지. 우리조에서는 2개의 경우를 모두
만들어놓고 첫 번째 방법으로 완성시켰다.

�ݺ�ߣ

2012 Ds B2 05

Recommended

More Related Content

What's hot (11)

Viewers also liked (17)

Similar to 2012 Ds B2 05 (20)

2012 Ds B2 05