RedJini Blog

#define M    65535 #define MAX    10 int path_info[MAX][MAX]={          { 0, 1, 4, 2, 9, M, M, M, M, 3},     //a    0      { 1, 0, M, M, 7, M, M, 5, M, M},     //b    1      { 4, M, 0,11, M, M, 4, M, M, M},     //c    2      { 2, M,11, 0, M, 1, M, M, M, M},     //d    3      { 9, 7, M, M, 0, 2, M, 1, M, 3},     //e    4      { M, M, M, 1, 2, 0, 2, M, 5, 4},     //f    5      { M, M, 4, M, M, 2, 0, M, 7, M},     //g    6      { M, 5, M, M, 1, M, M, 0, M, 2},     //h    7      { M, M, M, M, M, 5, 7, M, 0, 3},     //i    8      { 3, M, M, M, 3, 4, M, 2, 3, 0}      //j    9     }; int dijkstra(char start, char end){     int di   [MAX]={M, M, M, M, M, M, M, M, M, M};     int chk  [MAX]={0, 0, 0, 0, 0, 0, 0, 0, 0, 0};     int pre  [MAX]={0, 0, 0, 0, 0, 0, 0, 0, 0, 0};     if(start < 'a' || start > 'j') return -1;     if(end   < 'a' || end   > 'j') return -1;     int start_idx = start-'a';     int end_idx   = end  -'a';     int idx = 0;     /*최단거리 탐색*/     di[start_idx] = 0;     for(int i=0; i<MAX; i++){         unsigned int min = M;         for(int j=0; j<MAX; j++){             if( (chk[j]==0) && (di[j] < min)){                 idx= j;                 min= di[j];             }         }         chk[idx]=1;         if(min==M){             return -1;         }         for(int j=0; j<MAX; j++){             if( di [j] > di[idx]+path_info[idx][j]){                 di [j] = di[idx]+path_info[idx][j];                 pre[j] = idx;             }         }         if(idx==end_idx){             break;         }     }     //최단거리 탐색     //탐색 경로 출력     int pre_idx;     int top;     int pre_path[MAX]={0, 0, 0, 0, 0, 0, 0, 0, 0, 0};     for(int i=0; i<MAX; i++){         pre_idx = i;         top = 0;         if(pre_idx!=start_idx){             if(chk[i]>0){                 do{                     pre_path[top++] = pre_idx;                     pre_idx            = pre[pre_idx];                 }while(pre_idx!=start_idx);                 pre_path[top]=pre_idx;                 while(top >= 0){                     printf("%c[%d]", pre_path[top]+'a', pre_path[top]);                     if(top--!=0){                         printf("->");                     }                 }                 printf("\n");             }         }     }     //탐색 경로 출력     printf("\n %c=>%c :%d", start, end, di[end_idx]);     return 0; }

참고사이트 : http://ko.wikipedia.org/wiki/%eb%8d%b0% ··· 5a6%2598