소스코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 | #define M 65535#define MAX 10int 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;} |
참고사이트
"프로그래밍 / Visual C" 분류의 다른 글
| [MFC] HttpOpenRequest 이용시 0xC0000005: 0xcccccccc 오류 (0) | 2014/03/04 |
| [MFC] modal dialog(모달 대화상자) 숨긴채로 시작하기 (0) | 2014/03/04 |
| [MFC] 프로세스 파일 경로 (0) | 2013/09/24 |
| [MFC] OpenSSL Visual Studio 2008에서 컴파일 및 설치 하기 (0) | 2009/05/11 |
| [MFC] Visual Studio 2008에서 zlib 1.2.3 컴파일 (0) | 2009/04/21 |
| IE8설치후 VS2008 스크립트 오류 문제 (4) | 2009/03/31 |
| Microsoft Office 2007 연동 (1) | 2008/06/04 |
| GDI+에서 Round Rectangle 그리기. (0) | 2008/03/14 |
| VC macro __FUNCTION__ UNICODE에서 사용하기 (0) | 2008/03/14 |
| MulDiv (0) | 2007/12/12 |