[알고리즘] 다익스트라 알고리즘, Dijkstra's Algorithm | 설계 및 분석, 구현코드

  다익스트라 알고리즘은 가중치가 있는 방향성 그래프에서 한 특정 정점에서 다른 모든 정점으로 가는 최단경로를 구하는 문제이다. 앞서 살펴본 프림 알고리즘, 크루스칼 알고리즘과 마찬가지로 최단 경로를 구하는 문제이며 그래프를 사용한다는 점에서 공통점이 있지만 다익스트라 알고리즘은 Minimum Spanning Tree를 구하는 문제가 아니라는 점에서 차이가 있다.

  아래의 수도코드를 보면 프림 알고리즘의 수도코드와 유사하다는 것을 알 수 있지만, 이미 방문한 집합 V-Y에서부터 정점  v까지의 최단거리를 선택하는 프림 알고리즘과 달리 다익스트라 알고리즘은 출발점부터 정점 v까지의 최단거리를 구한다.

 

수도코드(high level)

 

F:=∅
Y:={v1};

while(the instance is not solved)
  select a vertex from V-Y, that has a shortest path from v1, //selection procedure
  using only vertices in Y as intermediate; //reasibility check
  
  add the new vertex v to Y;
  add the edge (on the shortest) that touches v to F;
  
  if(Y==V)  //solution check
    the instance is solved;
  

 

  위 수도코드를 보면 'a shortest path from v₁'에서 알 수 있듯 집합이 아닌 오직 한 정점(출발점)에서부터 가까운 정점을 구하고있다. 따라서 '이미 방문한 정점들의 집합 Y 내의 정점을 거쳐가는 경우'까지 고려하여 출발점에서부터 정점까지의 거리를 구한다. 이는 'using only verticies in Y as intermediate'에서 알 수 있다.

 

문제 해결 과정

  dijkstra 알고리즘은 touch배열과 length배열을 추가적으로 사용하는데, 이는 각각 prim 알고리즘의 nearest 배열과 distance 배열에 대응한다.

• touch[i] : 출발점에서부터 v_i까지의 경로 상에 놓인 정점 중 가장 마지막 정점의 인덱스 (가장 마지막에 터치한 정점의 인덱스)
• length[i] : 출발점과 v_i까지 놓인 이음선의 가중치. 즉, 출발점과 v_i까지의 거리

  그래프와 touch 배열, length 배열 사용하여 문제 해결 과정의 예시를 보이면 다음과 같다.

 

문제 해결 과정 예시

  위 과정을 보면 알 수 있듯이 그래프는 크게 방문한 정점들의 집합 Y와, 방문하지 않은 정점들의 집합 V-Y 이렇게 두 묶음으로 나뉜다. 집합 V-Y의 정점들 중 출발점과 가장 가까운 정점을 선택하여 이를 집합 Y에 포함한다. 새로운 정점이 집합 Y에 포함되고 나면 아직 방문하지 않은 집합 V-Y 정점들의 length 배열 값을 갱신한다. 새로운 정점을 통해 출발점과 연결되는 경로가 더 짧아졌을 수도 있기 때문이다.

  이 과정을 기억하고 아래의 수도코드를 이해해보자.

 

수도코드(low level) 

 

void dijkstra (int n, const number W[][], set_of_edges& F) {
  index i, vnear; edge e;
  index touch[2..n]; number length[2..n];
  
  F=∅;
  for(i=2; i<=n; i++) {
    touch[i] = 1;
    length[i] = W[1][i];
  }
  
  repeat(n-1 times) { //출발점을 제외한 정점의 수는 n-1개이므로 최대 n-1번 수행
    min = "infinite";
    for(i=2; i<=n; i++) //V-Y 집합의 정점들 중 출발점과 가장 가까운 정점 찾기
      if(0 <= length[i] <= min) { 
        min = length[i]; //출발점에서부터 정점까지의 거리 저장 
        vnear = i; //정점의 인덱스 저장
      }
    
    //가장 가까운 정점을 찾은 후
    e = edge from vertex indexed by touch[vnear] to vertex indexed by vnear;
    add e to F; //F에 edge저장
    
    
    for(i=2; i<=n; i++) //다른 정점들의 값도 새로 갱신할지 여부 결정
      if(length[vnear] + W[vnear][i] < length[i]) { //V-Y집합 내의 모든 정점에 대해 Y집합에 새로 추가된 정점을 지나는게 더 빠른지, 기존의 경우가 더 빠른지 각각 비교
        length[i] = length[vnear] + W[vnear][i];
        touch[i] = vnear;
      }
    length[vnear] = -1;
  }
}

 

알고리즘 분석

  위 알고리즘 코드를 보면 dijkstra 알고리즘의 구조가 prim 알고리즘의 구조와 같음을 알 수 있다. 따라서 성능 또한 prim 알고리즘과 같다.

 

basic operation : length 값을 비교하는 부분(두 개의 for문 내부의 명령문)
dijkstra 알고리즘은 그래프의 내용에 상관없이 연산횟수가 동일한 every-case이다.
각 for문은 n-1번 반복되므로 2x(n-1)이고 이는 n-1번 반복하는 reapeat에 싸여있으므로 2x(n-1)x(n-1)
∴ T(n) = 2(n-1)(n-1) ∈ Θ(n²)

 

구현 코드

 

#include <stdio.h>

typedef struct
{
	int weight;
	int v1;
	int v2;
}edge;

#define N 5
#define INF 1000

void dijkstra(int n, int(*W)[N + 1], edge* F);

int f_index = -1;

int main()
{
	int W[N + 1][N + 1] = { {0,0,0,0,0,0},
						{0,0,7,4,6,1},
						{0,INF,0,INF,INF,INF},
						{0,INF,2,0,5,INF},
						{0,INF,3,INF,0,INF},
						{0,INF,INF,INF,1,0}
	};


	edge F[N];

	dijkstra(N, W, F);

	for (int i = 0; i < f_index; i++)
	{
		printf("%d - %d\n", F[i].v1, F[i].v2);
	}
}


void dijkstra(int n, int (*W)[N+1], edge *F)
{
	int vnear;
	edge e;

	int touch[N + 1];
	int length[N + 1];

	for (int i = 2; i <= n; i++)
	{
		touch[i] = 1;
		length[i] = W[1][i];
	}

	while (1)
	{


		int min = INF;
		for (int i=2; i <= n; i++)
		{
			if (0 <= length[i] && length[i]<= min)
			{
				min = length[i];
				vnear = i;
			}
		}
		
		e.v1 = touch[vnear];
		e.v2 = vnear;

		F[++f_index] = e;

		for (int i = 2; i <= n; i++)
		{
			if (length[vnear] + W[vnear][i] < length[i])
			{
				length[i] = length[vnear] + W[vnear][i];
				touch[i] = vnear;
			}
		}
		length[vnear] = -1;

		if (f_index == n - 1)
			break;
	}
}