/ C

알고리즘 정복하기 with C (5)Dijkstra Algorithm

알고리즘 정복하기 with C (5)Dijkstra Algorithm

직접 코딩하면서 자료구조 공부하기

개요

자료구조와 알고리즘은 프로그램을 구성하는 가장 핵심적인 요소입니다. 프로그램 개발을 집을 짓는 것에 비유한다면 흙이나 모래, 시멘트, 목재와 같은 자재들이 바로 ‘자료구조’에 해당되고, 이러한 자재들을 이용해서 집을 짓는 것이 ‘알고리즘’에 해당됩니다. 알고리즘은 가장 기본적이고 중요한 부분이기 때문에 복습하는 겸해서 직접 여러가지 알고리즘을 코딩하면서 공부하기로 했습니다.

Dijkstra Algorithm

다익스트라 알고리즘은 가중치가 있는 방향성 그래프에서 한 특정 정점에서 다른 모든 정점으로 가는 최단경로를 구하는 문제입니다. 프림 알고리즘, 크루스칼 알고리즘과 마찬가지로 최단 경로를 구하는 문제이며 그래프를 사용한다는 점에서 공통점이 있지만 다익스트라 알고리즘은 Minimum Spanning Tree를 구하는 문제가 아니라는 점에서 차이가 있습니다. 이미 방문한 집합 V-Y에서부터 정점 v까지의 최단거리를 선택하는 프림 알고리즘과 달리 다익스트라 알고리즘은 출발점부터 정점 v까지의 최단거리를 구합니다.

Dijkstra Algorithm pseudo code

Dijkstra Algorithm 의 pseudo code

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 Algorithm 시간 복잡도

n - 1 while 루프에 n-1 for문이 두번 있으므로 2 * (n-1) * (n-1) = O(n^2) 이다.

Dijkstra Algorithm 구현

입력데이터

소스코드

#include <stdio.h>
#include <stdbool.h>

#define N 6

typedef struct edgeList {
	int weight;
	int first_vertex;
	int second_vertex;
}edgeList;

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

int f = 0;

int main()
{
	int W[N + 1][N + 1] = { {0,0,0,0,0,0,0},
							{0,0,2,5,1,999,999},
							{0,999,0,3,2,999,999},
							{0,999,999,0,3,999,5},
							{0,999,999,999,0,1,999},
							{0,999,999,1,999,0,2},
							{0,999,999,999,999,999,0} };

	edgeList F[N];

	dijkstra(N, W, F);

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


void dijkstra(int n, int(*W)[N + 1], edgeList* F)
{
	int vnear;
	edgeList 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 (f != n-1) {
		int min = 999;
		for (int i = 2; i <= n; i++) {
			if (0 <= length[i] && length[i] <= min) {
				min = length[i];
				vnear = i;
			}
		}

		e.first_vertex = touch[vnear];
		e.second_vertex = vnear;

		F[f] = e;
		f++;

		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;
	}
}

결과

Dijkstra 알고리즘과 출력을 구현했습니다. 결과가 잘 나옵니다.

알고리즘 진행 과정 손계산

알고리즘의 진행과정을 직접 계산하여 결과를 비교해보았습니다. 결과가 동일하게 나옵니다.