CPP > 데이크스트라 알고리즘(Dijkstra algorithm)

소스코드

#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;
}

참고

• 데이크스트라 알고리즘