동적 계획법-플로이드 알로리즘

소개글

동적 계획법-플로이드 알로리즘에 대한 보고서 자료입니다.

목차

1.개 요

2.플로이드 알고리즘에 사용된 자료구조

3.플로이드 알고리즘의 문제 해결 방법

4.예 시

5.방 법

6.플로이드 알고리즘의 의사코드

7.플로이드 알고리즘의 의사코드(최단거리 경로 추가)

8.최단경로 출력

본문내용

1.72}
,{100,100,100,100,100,6.28,100,100,5.06,3.9,100,100,1.72,0} };
//제공된 테이블을 직접 입력하였습니다.
void main()
{
int start,finish;
printf("출발할 도시와 도착할 도시 입력 ex)1~5\n");
scanf("%d~%d",&start,&finish);
printf("출발할 도시 %d이고 도착할 도시 %d \n",start,finish);
start--;
finish--;
//위치보정(도시는 1부터 있는데 c++은 0부터 시작하기 때문에 위치를 보정해 주었습니다.)
//그러니까 4라는 도시에서 출발하는데 4라고 치면 실제로는 3이라는 도시로 출발하기때문에
//start--;finish--; 를 사용하여 위치를 교정해 주었습니다.
int i,k;
double min;
struct node_info city[14];
/* table 값 대칭 확인
for (i=0; i<14;i++)
for (j=0; j<14;j++)
if(dist_table[i][j] != dist_table[j][i])
printf("%d,%d ", i,j);
*/
for (i=0; i<14;i++)
{
city[i].dist = dist_table[finish][i];
city[i].from = finish;
city[i].flag = 0;
}
// 마지막 노드를 초기화
city[finish].dist = 0;
city[finish].from = finish;
city[finish].flag = 1;
int p = finish;//마지막 노드부터 역추적
for(i=0;i<12;i++)//
{
min = 100;
for (k=0;k<14;k++)
{
if ((city[k].flag == 0)&&(min > city[k].dist))
{
min = city[k].dist;//if문을 사용하여 더 작은 min있으시 교환
p = k;
}
}//마지막노드와 가장 가까운 노드 찾기
city[p].flag = 1;
for (k=0;k<14;k++)// 위에서 찾은 노드로 나머지에 대한 거리 재계산
{
if(city[k].dist > (min + dist_table[p][k]))//종점에서 현위치 까지의 거리
{
city[k].dist = min + dist_table[p][k];
city[k].from = p;
}
}
}
/*
for (k=0;k<14;k++)
{
printf("%d ", city[k].from);
}
*/
printf("도시 %d과 도시 %d의 최단 거리는 %f입니다. \n" , start+1, finish+1, city[start].dist );
printf("그리고 최단경로는 \n입니다.");
p = start;
while(true) //시작노드부터 차례로 화면에 출력
{
printf("%d => ", p +1);
p = city[p].from;
if (p == finish)
{
printf("%d 이다.\n", p+1);
break;
}
}
return;
}

키워드

동적 계획법,   플로이드,   알로리즘,   조선해양공학,   다익스트라,   그리디,   의사코드,   최단거리