#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
wiki에서도 어떻게 implement하는지 잘 안나와있어서 헤메고 있었는데. 님 코드를 보니 대략 이해가 가네여. 아, 저는 java배우고있는 고딩이에여 ㅎ 감사합니다.
왼쪽에 라인 나오고 이런식으로 코드 올리는것을 많이 봤는데 무슨 플러그인인가요? 궁금합니다.
Name Password
URI
Non-public
Leave your greetings.
wiki에서도 어떻게 implement하는지 잘 안나와있어서 헤메고 있었는데.
2010/02/05 13:26 [ Permalink : Modify/Delete : Reply ]님 코드를 보니 대략 이해가 가네여.
아, 저는 java배우고있는 고딩이에여 ㅎ
감사합니다.
왼쪽에 라인 나오고 이런식으로 코드 올리는것을 많이 봤는데 무슨 플러그인인가요?
2010/06/10 18:01 [ Permalink : Modify/Delete : Reply ]궁금합니다.