수다닷컴

#includestdio.h
#define MAX_NODES 1024
#define INFINITY 100000000
void shortest_path(int s, int t, int path[]);
int n=8;

int dist[MAX_NODES][MAX_NODES] =
{{0,2,6,INFINITY,INFINITY,INFINITY,INFINITY,INFINITY},
{2,0,INFINITY,2,INFINITY,7,INFINITY,INFINITY},
{6,INFINITY,0,1,INFINITY,INFINITY,4,INFINITY},
{INFINITY,2,1,0,2,INFINITY,INFINITY,INFINITY},
{INFINITY,INFINITY,INFINITY,2,0,3,2,INFINITY},
{INFINITY,7,INFINITY,INFINITY,3,0,INFINITY,3},
{INFINITY,INFINITY,4,INFINITY,2,INFINITY,0,2},
{INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,3,2,0}};
int main()
{
int s,e;
int v[8]={0};
printf(\n 다익스트라(Dijkstra) 알고리즘 \n);
printf(\n 주어진 그래프에서 출발점과 도착점을 입력하면 최단거리를 알려줍니다.);
printf(\n +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++);
printf(\n + +);
printf(\n + [2]-------------7-----------[6] +);
printf(\n + ( ) ( ) +);
printf(\n + ( ) ( ) +);
printf(\n + 2 2 3 3 +);
printf(\n + ( ) ( ) +);
printf(\n + ( ) ( ) +);
printf(\n + [1] [4]------2-----[5] [8] +);
printf(\n + ( ) ( ) +);
printf(\n + ( ) ( ) +);
printf(\n + 6 1 2 2 +);
printf(\n + ( ) ( ) +);
printf(\n + ( ) ( ) +);
printf(\n + [3]-------------4------------[7] +);
printf(\n + +);
printf(\n +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n);
////////////////////////////////////////////////////////////////////////////////////

while(1)
{
printf(\n 출발점을 입력하시오. : );
scanf(%d, &s);
printf(\n 도착점을 입력하시오. : );
scanf(%d, &e);
//printf( %d -, s);
shortest_path(s-1, e-1, v);
}
return 0;
}
void shortest_path(int t, int s, int path[])
{

struct state {
int predecessor;
int lengh;
enum {permanent, tentative} lable;
}state[MAX_NODES];

int i,k,min;
struct state *p;
for(p=&state[0]; p&state[n]; p++)
{
p-predecessor = -1;
p-lengh = INFINITY;
p-lable = tentative;
}

state[t].lengh = 0;
state[t].lable = permanent;
k = t;
do {
for(i=0;in;i++)
{
if(dist[k][i] != 0 && state[i].lable == tentative) {
if(state[k].lengh + dist[k][i] state[i].lengh) {
state[i].predecessor = k;
state[i].lengh = state[k].lengh + dist[k][i];
}
}
}

k=0;
min = INFINITY;

for(i=0;in;i++)
{
//임시 노드이고 최소값보다 작으면.
if(state[i].lable == tentative && state[i].lengh min) {
//최소값에 대입
min = state[i].lengh;
k=i;
}
}

state[k].lable = permanent;
//if(k==s) printf(%d, k+1);
//else printf( %d - , k+1);
}while(k!=s);
i=0;
k=s;
do {
path[i++] = k;
k=state[k].predecessor;
}while(k=0);
printf(\n\n %d에서 %d 까지의 최단거리비용은 - %d \n, t+1,s+1,state[s].lengh);
}

신청하기