수다닷컴

최단경로와 최단거리를 구하는 알고리즘 인데요...
실행시키면 에러는 안나는데요...
최단경로랑 최단거리가 잘못나오거든요..
수정좀 해주세요

#include stdio.h
#define n 7
#define x 1000
void min_path(int W[7][7], int touch[7], int length[7]);
// 인접한 역의 거리를 나타낸 행열
// W[a][b] = 정점a에서 정점b 까지의 거리
// a, b가 직접 연결되있지 않으면 x값을 준다.
int W[7][7] = {
{0,11,9,x,3,x,x},
{x,0,x,x,6,x,30},
{x,x,0,x,19,12,x},
{x,x,x,0,x,x,21},
{x,x,4,16,0,21,44},
{x,x,x,x,x,0,8},
{x,x,x,x,x,x,0}};
// 역이름
char *s[7]={ [0] , [1] , [2] , [3] , [4] , [5] , [6] };

void main()
{
printf( . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . .\n);
printf( . Dijkstra 알고리즘 .\n);
printf( . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .\n);
printf( . .\n);
printf( . [2] . . . . . .12 . . . . . [5] .\n);
printf( . .^ ^. . . ^ . .\n);
printf( . . . . . . .\n);
printf( . 9. 4. .19 21. .18 .\n);
printf( . . . . . . .\n);
printf( . . . . .\n);
printf( . [0]. . . . 3. . . . [4]. . . .44 . . . . . . [6] .\n);
printf( . . ^ . . ^ .\n);
printf( . . . . . . .\n);
printf( . . . . 16 . . .\n);
printf( . 11 . . . . .\n);
printf( . . 6. . . . 21 .\n);
printf( . . . . 30 . . .\n);
printf( . . . . .\n);
printf( . [1]&nbsbsp; [3] .\n);
printf( . .\n);
printf( . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .\n);
int i;
// length[i] = start(출발점)에서 i번째 정점까지의 최단거리
// touch[i] = start정점부터 i번째 정점으로 가는 최단경로에서 i번째 경로의
// 바로 전 정점의 번호
int length[7],touch[7];

//역이름 출력
for(i=0;i7;i++)
printf(%s,s[i]);

//최단 경로를 구하는 함수 호출
min_path(W, touch, length);
}
//최단 경로를 구하는 함수
void min_path(int W[7][7], int touch[7], int length[7]){

int i, vnear, start, end, step, min_length;

//Y[i]=i번째 정점이 체크 되었는지 나타냄
int Y[7];

//배열 Y를 0으로 초기화
for(i=0; i7; i++){
Y[i] = 0;
length[i] = x;
}
//출발역과 도착역 저장
printf(\n출발점 : );
scanf(%d, &start);
printf(도착점 : );
scanf(%d, &end);

//시작점을 0으로 표시
length[start-1] = 0;
for(step=1; step=7; step++){
min_length = x;
for(i=0; i7; i++){
if(Y[i]==0 && length[i]min_length){
// vnear = 현재 length배열에 있는것중 값이 가장적은것이며 채크 안된거
vnear = i;
min_length = length[i];
}
}
Y[vnear] = 1;
for(i=1; i7; i++){
//length[i]보다 length[vnear] + W[vnear][i]가 작으면 갱신
if(length[i] length[vnear] + W[vnear][i]){
length[i] = length[vnear] + W[vnear][i];
touch[i]=vnear;
}
}
}

//경로를 찍어주는 부분
int path[7], path_cnt=0;
vnear=end;
while(1)
{
path[path_cnt++]=vnear;
if(vnear==start-1) break;
vnear=touch[vnear];
}
printf(\n최단 경로는 : );
for(i=path_cnt-1;i=1;i--)
printf(%s - ,s[path[i]]);
printf(%s 입니다.,s[path[i]]);
printf(\n(%s)에서 출발하여, (%s)(으)로 가는 최단 거리는 %d입니다.\n\n, s[start], s[end], length[end-1]);
}

신청하기