수다닷컴

시작 도시와 도착도시를 설정하고 최단거리를 출력하고 , 그 경로를 찍어서 나타내는겁니다
논리에도 문제가 있다면 좀 집어주십시오 ㅜ

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
#includestdio.h

#define INF 10000
#define TRUE 1
#define FALSE 0
int weight[20][20];
int found[20];
void InitCity(); // 경로상의 도시들을 출력.
int Dijstra(int start, int n, int arrive);
int select(int distance[], int n, int found[]);
int distance[20];
int i=0;
int j=0;
int weight[20][20]={{0,1,2,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,4,3,INF},
{1,0,INF,4,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,8,11,INF,INF},
{2,INF,0,INF,INF,INF,INF,INF,INF,8,INF,INF,2,INF,INF,INF,INF,INF,7,INF},
{INF,INF,4,INF,0,INF,INF,INF,INF,INF,6,INF,INF,INF,INF,INF,INF,5,INF,INF},
{INF,INF,INF,INF,0,INF,INF,INF,INF,INF,9,INF,INF,12,INF,3,INF,INF,INF,INF},
{INF,INF,INF,INF,INF,0,5,INF,INF,INF,3,INF,INF,2,1,INF,INF,INF,INF,INF},
{INF,INF,INF,INF,INF,5,0,2,INF,INF,INF,INF,INF,INF,4,INF,INF,INF,INF,INF},
{INF,INF,INF,INF,INF,INF,2,0,12,INF,INF,7,INF,INF,INF,INF,INF,INF,INF,INF},
{INF,INF,INF,INF,INF,INF,INF,12,0,INF,INF,INF,10,INF,INF,INF,INF,INF,INF,INF},
{7,INF,8,6,INF,INF,INF,INF,INF,0,2,INF,INF,INF,INF,INF,INF,INF,INF,INF},
{INF,INF,INF,INF,9,3,INF,INF,INF,2,0,8,INF,INF,INF,INF,INF,INF,INF,INF},
{INF,INF,INF,INF,INF,INF,INF,7,INF,INF,8,0,1,INF,INF,INF,INF,INF,INF,INF},
{INF,INF,2,INF,INF,INF,INF,INF,10,INF,INF,1,0,INF,INF,INF,INF,INF,INF,11},
{INF,INF,INF,INF,12,2,INF,INF,INF,INF,INF,INF,INF,0,11,16,INF,INF,INF,INF},
{INF,INF,INF,INF,INF,1,4,INF,INF,INF,INF,INF,INF,11,0,INF,INF,INF,INF,INF},
{INF,INF,INF,4,3,INF,INF,INF,INF,INF,INF,INF,INF,16,INF,0,INF,INF,INF,INF},
{INF,8,INF,5,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,0,6,INF,INF},
{4,11,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,6,0,INF,INF},
{3,INF,7,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,0,1},
{INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,11,INF,INF,INF,INF,INF,1,0} };void TrackPath();int main(void)
{
int s=0;
int t=0;
int n=20;printf(Select start City : \n);
scanf_s(%d,&s);
printf(Select arrive City : \n);
scanf_s(%d,&t);printf(The shortest path is %d\n,Dijstra(s,n,t));

}void InitCity()
{

int City[20]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};

for(i=0;i20;i++)
{
printf(City[%d] = %d\t\n,i+1,City[i]);
}

}

int Dijstra(int start , int n, int arrive)
{
int i=0;
int u=0;
int w=0;
for(i=0;in;i++)
{
distance[i]=weight[start][i];
found[i]=FALSE;
}
found[start]=TRUE;
distance[start]=0;
for(i=0;in-2;i++)
{
u=select(distance,n,found);
found[u]=TRUE;if(!found[w])
{
if(distance[u]+weight[u][w]distance[w])
distance[w]=distance[u]+distance[u][w];//첨자 또는 배열 또는 포인터형식을 사용해야한답니다
.
.}
TrackPath(distance[w]); // 제가 생각하기로는 여기서 최단경로의 path 를 하나씩 펑션콜해서 출력
}

arrive = distance[arrive-1];
return arrive;
}

int select(int distance[], int n, int found[])
{
int i=0;
int min=1000;
int minpos=-1;
for(i=0;in;i++)
if(distance[i]min&&!found[i])
{
min=distance[i];
minpos=i;
}
return minpos;
}

void TrackPath(int vertex)
{

printf(Path : %d \n,vertex);
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

신청하기