그래프 관련인듯

#include<stdio.h>

#define MAX_VERTICES 6

#define IF 1000

#define FALSE 0

#define TRUE 1

void shortestPath(int v, int cost[][MAX_VERTICES],int distance[],int n, short found[]);

int choose(int distance[], int n, short int found[]);

int distance[MAX_VERTICES];

int uu[6];

int parent[MAX_VERTICES];

int short found[MAX_VERTICES];

int length[MAX_VERTICES];

int cost[MAX_VERTICES][MAX_VERTICES]={

//  0   1    2 3 4   5   

0 , 50 , 45, 10, IF, IF,

IF, 0  , 10, 15, IF, IF,

IF, IF,  0,  IF, 30, IF,

20, IF,  IF, 0,  15, IF,

IF, 20,  35, IF,  0, IF,

IF, IF,  IF, IF,  3, IF

};

int top=0;

int main(void)

{

int i,j,k,min,temp;

shortestPath(0,cost, distance,MAX_VERTICES,found);

printf("parent");

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

{

printf("\t%d",parent[i]);

}

printf("\n");

printf("child");

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

printf("\t%d",i);

min = IF;

printf("\n");

for(i=0;i<=top-1;i++)

{

printf("length = %d\tpath: ",length[i]);

printf("%d",uu[i]);

temp=uu[i];

while(parent[temp]!=-1)

{

printf(" %d",parent[temp]);

temp=parent[temp];

}

printf("\n");

}

return 0;

}

void shortestPath(int v, int cost[][MAX_VERTICES],int distance[],int n, short found[])

{

int i,u,w;

int count=0;

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

{

parent[i]= -1;

found[i] = FALSE;

distance[i] = cost[v][i];

}

found[v] = TRUE;

distance[v] = 0;

for( i =0; i< n-2; i++)   //0~3 까지

{

u=choose(distance,n,found);

if(parent[u] == -1)

{

parent[u] = 0;

}

found[u] = TRUE;

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

{

printf("%d\t",distance[w]);

if(!found[w])

{

if(distance[u] + cost[u][w] < distance[w])

{

distance[w] = distance[u] + cost[u][w];

parent[w]=u;

}

}

}

uu[top]=u;

length[top++]=distance[u];

printf("\n");

}

}

int choose(int distance[], int n, short int found[])

{

int i,min,minpos;

min = IF;

minpos = -1;

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

{

if(distance[i]<min&&!found[i])

{

min= distance[i];

minpos = i;

}

}

return minpos;

}