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

프로그래밍/Visual C 2008/12/29 13:08 [54144] 글쓴이 : 나그네

소스코드

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
2008/12/29 13:08 2008/12/29 13:08
태그 : , ,
걸린 글 0 / 덧글 2
글 걸기 주소 : 이 글에는 트랙백을 보낼 수 없습니다

GCC virtual method 컴파일 문제

프로그래밍/기타 2008/12/03 18:41 [38135] 글쓴이 : 나그네

1
2
3
4
5
6
7
8
9
10
class a{
public:
    a(){}
    ~a(){}
    virtual void test() = 0;
}
 
class b : public a{
    virtual void test(){printf("test");}
}

위와 같이 선어후 컴파일 할경우 GCC에서
warning: ‘class a’ has virtual functions but non-virtual destructor
와 같은 경고 메세지를 출력한다.

class a의 소멸자에 virtual을 붙여주자

1
2
3
4
5
6
7
8
9
10
class a{
public:
    a(){}
    virtual ~a(){}
    virtual void test() = 0;
}
 
class b : public a{
    virtual void test(){printf("test");}
}

"프로그래밍 / 기타" 분류의 다른 글

Textcube 카테고리 목록 출력시 등록된 글의 공개/비공개/발행 여부를 출력하기 (0)2014/01/06
Textcube 1.9.0에 TinyMCE 4.0.11 적용하기 (0)2013/12/03
uname (0)2008/12/01
Apache 특정 파일 및 하위 디렉토리 접근 제한 (0)2008/11/07
.htaccess 활용~ (0)2008/01/28
cannot restore segment prot after reloc: Permission denied (0)2007/05/23
PuTTY에서 한글 입력하기 (0)2007/04/18
PHP SOAP Client 만들기 (0)2007/03/06
윈도우 배치파일을 이용한 백업? (0)2007/01/25
javascript String Trim (0)2006/08/23
2008/12/03 18:41 2008/12/03 18:41
태그 : , , ,
걸린 글 0 / 덧글 0
글 걸기 주소 : 이 글에는 트랙백을 보낼 수 없습니다

uname

프로그래밍/기타 2008/12/01 15:03 [36687] 글쓴이 : 나그네
이름
    uname - 현재 커널에 관한 이름과 정보를 얻어온다.

사용법
    #include <sys/utsname.h>
    int uname(struct utsname *buf);

설명
    uname은 buf가가리키는 구조체에 시스템 정보를 리턴한다.  utsname 구조체는 다음과 같다. 
    <sys/utsname.h>:
    struct utsname {
                char sysname[SYS_NMLN];
                char nodename[SYS_NMLN];
                char release[SYS_NMLN];
                char version[SYS_NMLN];
                char machine[SYS_NMLN];
          #ifdef _GNU_SOURCE
                char domainname[SYS_NMLN];
          #endif
    };

반환값
    성공시, 0이 리턴된다. 에러시, -1이 리턴되며 errno가적절한 값으로 설정된다.

에러
    EFAULT buf가유효하지 않다.

호환
    SVr4, SVID, POSIX, X/OPEN
    domainname 변수는 GNU 확장이다.

관련 항목
    uname(1), getdomainname(2), gethostname(2)

셈플 소스

1
2
3
4
5
6
7
8
9
  struct utsname buf;
  uname(&buf);
 
  printf("sysname    %s\n", buf.sysname   );
  printf("nodename   %s\n", buf.nodename  );
  printf("release    %s\n", buf.release   );
  printf("version    %s\n", buf.version   );
  printf("machine    %s\n", buf.machine   );
  printf("domainname %s\n", buf.domainname);

출력 결과

    sysname    Linux
    nodename   redjini.com
    release    2.6.18-8.el5
    version    #1 SMP Thu Mar 15 19:57:35 EDT 2007
    machine    i686
    domainname (none)

"프로그래밍 / 기타" 분류의 다른 글

Textcube 카테고리 목록 출력시 등록된 글의 공개/비공개/발행 여부를 출력하기 (0)2014/01/06
Textcube 1.9.0에 TinyMCE 4.0.11 적용하기 (0)2013/12/03
GCC virtual method 컴파일 문제 (0)2008/12/03
Apache 특정 파일 및 하위 디렉토리 접근 제한 (0)2008/11/07
.htaccess 활용~ (0)2008/01/28
cannot restore segment prot after reloc: Permission denied (0)2007/05/23
PuTTY에서 한글 입력하기 (0)2007/04/18
PHP SOAP Client 만들기 (0)2007/03/06
윈도우 배치파일을 이용한 백업? (0)2007/01/25
javascript String Trim (0)2006/08/23
2008/12/01 15:03 2008/12/01 15:03
태그 : ,
걸린 글 0 / 덧글 0
글 걸기 주소 : 이 글에는 트랙백을 보낼 수 없습니다