다익스트라(dijkstra) 알고리즘

다익스트라(Dijkstra)

- 가중치 그래프에 대해 최단거리 문제를 해결하기 위한 알고리즘

- 변 경감(edge relaxaxtion) 연산을 바탕으로 한다.

- 그래프의 가중치가 음수가 아니라고 가정한다.

- Extract-Min(Q) 함수를 단순한 선형 탐색으로 구현하면 O(n²)의 복잡도를 가진다.

- 이진 힙 또는 피보나치 힙을 통해 구현하면 O(m+nlogn) 시간까지 개선할 수 있다.

1. 동작 원리

- 각 꼭짓점 v에 대해 시작점(s)에서 끝점까지의 최단 거리 d[v]를 갱신하며 수행한다.

(1) 시작점(s)의 거리를 0으로 하고, 다른 모든 꼭짓점들의 거리는 INF(무한)으로 한다.

(2) Q에 나머지 모든 꼭짓점들을 배정한다.

(3) Q가 비어있으면 수행을 끝낸다.(= 모든 꼭짓점을 방문했다.)

(4) Q에서 꼭짓점 중 최단 거리에 있는 꼭짓점을 꺼낸다.

(5) 꺼내온 꼭짓점을 기준으로, 인접한 점들의 최단거리를 갱신한다.

(6) (2-5) 과정을 반복한다.

[ Fig. 1] 다익스트라 동작원리 - 출저 : Introduction to algorithms 3/E

 

Fig. 1을 살펴보면, 회색 꼭짓점은 현재 스택에서 꺼내어져, 인접 꼭짓점들의 거리를 계산하기 위한

기준이된다. 검은색 꼭짓점은 이미 방문이 끝난 지점을 의미한다.

2. 함수 설명

dijkstra() : 다익스트라 알고리즘의 몸통 부분으로, 동작원리 (2) 와 (3)의 기능을 수행한다.

extract_min() : 최단거리에 있는 꼭짓점을 구하는 기능을 수행한다. 기능 (4)에 해당한다.

relax() : 변 경감 연산을 바탕으로 최단거리를 갱신한다. 기능 (5)에 해당한다.

3. 함수 구현

 

#include <stdio.h> #include <malloc.h> #define UNADJACENCY 0 #define INF   9999 #define UNDEFINED -1 void malloc_arry( int, int); void release_arry( int); void dijkstra( int, int); void enqueue( int); void relax( int, int); void print_path( int); int queue_empty(); int extract_min( void); struct queue{  int *data;  int front;  int rear; }Q; int **w; // variable for memorizing weights between edges. int *d; // it saves information of the shortest direction. int *pre; // it is necessary to back track the root. /* 5 1 5 10 1 2 10 1 3 5 2 4 1 2 3 2 3 2 3 3 4 9 3 5 2 4 5 4 5 4 6 5 1 7 */ int main( void) {  int nov  = 0; // the number of vertexe  int startv = 0; // starting vertex.  int endv = 0; // the vertext of the end.  int noe  = 0; // the number of edges  int i;  int v = 0, n = 0, weight = 0;  scanf("%d%d%d", &nov, &startv, &endv);  scanf("%d", &noe);  malloc_arry( nov, noe);   for( i = 0 ; i < noe ; i ++)  {   scanf("%d%d%d", &v, &n, &weight);   w[v-1][n-1] = weight;  }  dijkstra( nov, startv-1);  printf("%d에서 %d까지의 최단 거리는 %d입니다.\n경로는", startv, endv, d[endv-1]);  print_path( endv-1);  printf("%d 입니다.\n", endv);  release_arry( nov);  return 0; } /*  allocate the memory to double point variable.  - we need nov * nov array.  - we will allocate the memory as much as we need. */ void malloc_arry( int nov, int noe) {  int i, j;    // it means that allocating the memory as much as the column of the array  w  = (int**)malloc(sizeof(int*) * nov);  // allocate the memory as much as the number of edges.  d  = (int*)malloc(sizeof(int*) * nov);  pre  = (int*)malloc(sizeof(int*) * nov);  // allocate the memory for the queue.  Q.data = (int*)malloc(sizeof(int*) * nov);  // allocate the memory as much as the row of the array  for( i = 0 ; i < nov ; i ++)  {   *(w + i) = (int *)malloc(sizeof(int) * nov);   // we have to init elements in the array with 0(zero).   for( j = 0 ; j < nov ; j ++)   {    *(*(w + i) + j) = 0;   }  } } /*  release the memory that we allocated the array. */ void release_arry( int nov) {  int i;  // Firstly. release the memory that related to the row  for( i = 0 ; i < nov ; i ++)  {   free(*(w+i));  }  // release the memory that related to directions.  free(d); free(pre); free(Q.data);  // Lastly, release the memory that related to the column  free(w); } /*  insert the vertext into the queue. */ void enqueue( int v) {  Q.data[Q.rear++] = v; } /*  examine whether the queue is empty or not */ int queue_empty() {  return Q.front == Q.rear; } void print_path( int v) {  if(pre[v] == UNDEFINED) return;  print_path( pre[v]);  printf(" %d >", pre[v]+1); } /*  find the nearest vertical */ int extract_min() {  int i, min = INF;  int j = 0;  int v = 0;  int pre, temp;  // search for the vertical in the queue.  for( i = Q.front ; i < Q.rear ; i ++)  {   // update the information about the vertical.   if( d[Q.data[i]] < min)   {    min  = d[Q.data[i]];    v  = Q.data[i];    j  = i;   }  }  // remove the element from the queue.  Q.data[j] = Q.data[Q.front];    Q.front ++;    return v; } /*  updates the distances of each edge with more shorter than previous distance. */ void relax( int u, int v) {  if( d[v] > (d[u] + w[u][v]))  {   d[v] = d[u] + w[u][v];   pre[v] = u;  } } /*  Dijkstra's Algorithms  - it find the shortest distances of each edge. */ void dijkstra( int nov, int s) {  int i = 0;  int u = 0;  // set the distance of other edges with INF.  for( i = 0 ; i < nov ; i ++)  {   d[i]  = INF;   // it is necessary to do back tracking   pre[i] = UNDEFINED;  }  d[s] = 0; // set the distance of starting point.  // insert vertexs into the queue except starting edge.  for( i = 0 ; i < nov ; i ++)  {   enqueue( i);  }  while( !queue_empty())  {   u = extract_min(); // find the nearest edge.   for( i = 0  ; i < nov ; i ++)   {    // find a adjacency vertical.    if( w[u][i] != UNADJACENCY)    {     relax( u, i);    }   }  } }

 

4. 실행 결과

Fig.1의 그림을 인접 배열로 표현한 결과, 아래와 같은 결과가 출력되는

것을 확인할 수 있다.