소스코드
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 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; } |
참고사이트
"프로그래밍 / 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 |