데이크스트라 알고리즘(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;
}
참고사이트