기출문제풀이 최단경로 알고리즘(shortest path algorithm, dijkstra) think Berry

2014.07.01 20:13

졸리운_곰 조회 수:682



[출처] http://thinkberry.co.kr/textyle/3376

최단경로 알고리즘(shortest path algorithm, dijkstra) think Berry

2010.12.25 12:58 왼손매직 Edit

  오늘은 흔히 알고리즘의 대가라고 불리는 크누님(=크누스)과 자주 언급되는 다익스트라의 최단경로 알고리즘을 다루어보겠습니다. 최근에는 자바스크립트를 손 놓고 옛 추억을 되짚고 있어 말이지요. 소스의 출저는 C로쓴 자료구조론이구요. 제 글보다는 관련 단원을 참고하시는게 수학적으로 더 확실합니다만 제 글로써 알고리즘을 이해하신다면 빌어먹을 수학기호와 해석할 수 없는 한글을 읽지 않고 절약된 시간으로 여러분의 인생을 좀 더 의미 있는 곳에 사용하실 수 있을겁니다. 보통 머리가 아파오는 알고리즘은 소스만 나열해놓아서는 그 의도를 파악하기가 쉽지 않습니다. 그래서 주절주절 정의와 수학적 표현을 기술하는데, 어찌된 일인지 이해를 돕기 위한 글이 의미를 알 수 없는 소스코드보다 더 읽기가 어렵습니다. 그럼 시작합니다.


  다익스트라의 최단경로 알고리즘은 갈망법(greedy method)으로 접근합니다. 갈망법은 눈 앞에 보이는데로 계속 최선의 선택을 하는 것입니다. 거시적 관점보다는 인간과 같이 눈 앞에 노인 상황에 탐욕적으로 접근한다고 하여 붙여진 이름이지요. 만약 최소비용신장트리의 프림 알고리즘을 알고 계신다면 이와 유사하다는 것을 느끼실 겁니다.

 

  다익스트라의 최단경로 알고리즘에서는 전제조건이 붙습니다. 정점(vertex)과 정점사이의 간선(edge)을 거치는 비용을 가중치(weight)라고 하는데 이 가중치는 음의 값이어서는 안된다는 것이죠. 만약 음의 값이 있었다간 그 구간을 무한히 돌며 블랙홀 속으로 빨려 들어가버릴 겁니다.



 1.jpg




음의 값이 오면 최단 경로가 무의미해집니다. 정점0과 1을 왓다갓다 하면 대체 끝이 어디죠?




  최단경로 알고리즘의 기본 아이디어는 다음과 같습니다.


 

0) 시작점을 '최단경로를 찾은 정점 리스트'에 담아둔다.

1) '최단경로를 찾은 정점 리스트'에 들어있는 정점으로부터 인접한 정점들중 가장 가중치가 적은 정점을 하나를 탐색한다. 이는 곧 해당 정점까지의 최단경로이다.

2)  리스트내에서의 정점들을 기준으로 가장 가중치가 적은 정점을 다시 탐색한다. 이때 발견되는 정점까지의 가중치는 직전 정점까지의 가중치 + 발견된 정정까지의 가중치로 계산된다. (엄밀히 말해 1.과 2.는 같다)

3) 가능한 모든 정점을 연결할 때까지 반복한다.


제가 제 글을 봐도 화가 나는군요. 한줄 요약으로 설명하겠습니다.

시작 정점부터 가장 가까운 정점을 선택하고 이를 리스트에 담아 기억하고 있다가 이들 정점들로부터 시작점으로부터의 가중치가 적은 간선 하나만 선택합니다. 계속 반복해서 모든 경로를 잇게 되면 시작점부터 모든 점까지의 최단경로는 모두 구해지는 것입니다. 그림으로 이해를 돕겠습니다.

경축! 아무것도 안하여 에스천사게임즈가 새로운 모습으로 재오픈 하였습니다.
어린이용이며, 설치가 필요없는 브라우저 게임입니다.
https://s1004games.com


 2_1.jpg








  그림을 보시는 바와 같이 최단경로 알고리즘은 시작점으로 부터 모든 정점까지의 최단거리를 계산할 수 있습니다. 시작점으로 부터 가장 가까운 거리의 정점을 우선 찾고 시작점부터 발견된 정점까지의 거리(가중치)를 별도로 기억합니다(distance). 그리고 발견된 모든 정점들로부터 가장 가중치가 적은 정점을 계속해서 찾아나감으로서 최적의 경로를 모두 탐색하는 것입니다. 핵심은 가중치가 누적되고, 가장 적은 가중치의 정점을 계속해서 찾아가는 이른바 갈망법인 것이죠.



 

다음은 C로 쓴 예제소스입니다. C로쓴 자료구조론의 최단경로절을 바탕으로 바로 돌려볼 수 있도록 약간 재구성되었습니다. 방향성 그래프는 2차원 배열로 표현되었습니다.


graph.dat 파일

view source
print?
01.7
02.0 1 5
03.0 3 10
04.1 2 5
05.1 4 20
06.2 4 10
07.3 4 20
08.3 5 30
09.6 3 20

소스코드 파일

view source
print?
001.#include<stdio.h>
002.#include<stdlib.h>
003.#include<limits.h>
004. 
005. 
006.#define BIG_INT     8192
007.#define MAX_SIZE    10
008.#define FOUND       1
009.#define NOT_FOUND   -1
010. 
011. 
012.void load_graph_from_file(char* filename, int graph[][MAX_SIZE], int* n);
013.int choose(int* distance, int* found, int n);
014.void shortest_path(int v, int graph[][MAX_SIZE], int* distance, int* found,int* pre_vertex,  int n);
015.void print_path(int* pre_vertex, int n);
016. 
017. 
018.int main(int argc, char** argv) {
019.    int graph[MAX_SIZE][MAX_SIZE];
020.    int distance[MAX_SIZE];
021.    int found[MAX_SIZE];
022.    int pre_vertex[MAX_SIZE];
023. 
024. 
025.    int v;
026.    int n;  // num of vertex
027. 
028. 
029.    load_graph_from_file("graph.dat", graph, &n);
030.    shortest_path(0, graph, distance, found, pre_vertex, n);
031.    print_path(pre_vertex, n);
032.    return 0;
033.}
034. 
035. 
036.void load_graph_from_file(char* filename, int graph[][MAX_SIZE], int* n) {
037.    FILE* fp = fopen(filename, "r");
038.    int v, w;   // start vertex, end vertex
039.    int weight;
040. 
041. 
042.    int i, j;
043. 
044. 
045.    if (fp == NULL) {
046.        printf("file not found exception.");
047.        exit(1);
048.    }
049.     
050.    fscanf (fp, "%d", n);
051.    if (*n > MAX_SIZE) { printf("too many vertex"); exit(1);}
052.     
053.    for (i=0; i<*n; ++i) {
054.        for (j=0; j<*n; ++j) {
055.            graph[i][j] = BIG_INT;
056.        }
057.    }
058. 
059. 
060.    while (!feof(fp)) {
061.        fscanf(fp,"%d %d %d",&v, &w,&weight);
062.        graph[v][w] = weight;
063.    }
064.}
065. 
066. 
067.int choose(int* distance, int* found, int n) {
068.    int i;
069.    int min = INT_MAX;
070.    int minpos = -1;
071. 
072. 
073.    for (i=0; i<n; ++i) {
074.        if (found[i] > NOT_FOUND) continue;
075.        if (distance[i] >=  min) continue;
076.         
077.        min = distance[i];
078.        minpos = i;
079.    }
080.    return minpos;
081.}
082. 
083. 
084.void shortest_path(int v, int graph[][MAX_SIZE], int* distance, int* found, int* pre_vertex, int n) {
085.    int i, u, w;
086.    //int pre_vertex;
087. 
088. 
089.    // init
090.    for (i=0; i<n; ++i) {
091.        distance[i] = graph[v][i];
092.        found[i] = NOT_FOUND;
093.        if ( distance[i] > 0 && distance[i] < BIG_INT) pre_vertex[i] = v;
094.        else pre_vertex[i] = -1;
095.    }
096. 
097. 
098.    distance[v] = 0;
099.    found[v] = FOUND;
100.     
101.    for (i=0; i<n-1; ++i) {
102.        u = choose(distance, found, n); //가장 가까운 정점을 찾는다.
103.        found[u] = FOUND;
104. 
105. 
106.        for (w=0; w<n; ++w) {        // 최단 경로상의 정점들로부터 인접정점들까지의 모든 distance를 계산한다.
107.            if (found[w] > NOT_FOUND) continue;
108.            if (distance[u] + graph[u][w] >= distance[w]) continue;
109. 
110. 
111.            distance[w] = distance[u] + graph[u][w];
112.            pre_vertex[w] = u;
113.        }
114.    }
115.}
116. 
117. 
118.void print_path(int* pre_vertex, int n) {
119.    int i;
120.    int cv; // current vertex
121.    for (i=0; i<n; ++i) {
122.        cv = i;
123. 
124. 
125.        printf("shortest path to %d :[%d]", cv, cv);
126.        while (pre_vertex[cv] >= 0) {
127.            printf("<-[%d]", pre_vertex[cv]);
128.            cv = pre_vertex[cv];
129.        }
130.        printf("\n");
131.    }
132. 
133. 
134.}

의문사항은 댓글로 남겨주시면 빠르게 답변해드리겠습니다.

~~ 메리 크리스마스



THinkBerry의 생각열매를 함께 나눠요. ThinkBerry.co.kr






본 웹사이트는 광고를 포함하고 있습니다.
광고 클릭에서 발생하는 수익금은 모두 웹사이트 서버의 유지 및 관리, 그리고 기술 콘텐츠 향상을 위해 쓰여집니다.
, , 이 게시물을
목록
목록
쓰기
태그
대표 김성준 주소 : 경기 용인 분당수지 U타워 등록번호 : 142-07-27414
통신판매업 신고 : 제2012-용인수지-0185호 출판업 신고 : 수지구청 제 123호 개인정보보호최고책임자 : 김성준 sjkim70@stechstar.com
대표전화 : 010-4589-2193 [fax] 02-6280-1294 COPYRIGHT(C) stechstar.com ALL RIGHTS RESERVED