<Dijkstra의 최단 경로 알고리즘> 기본개념과 알고리즘

# 최단 경로

---

 최단 경로(shortest path)문제는 정점 u와 정점 v를 연결하는 경로 중 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제다. 간선의 가중치는 경우에 따라 비용, 거리, 시간 등으로 해석될 수 있다.

 아래의 그래프를 살펴보자. 정점 0에서 정점 3으로 가는 최단 경로는 ( 0, 4, 1, 2, 3 )이고 이 때의 비용(거리)은 3 + 2 + 4 + 2 = 11 이다. 정점 0에서 정점 3으로 가는 다른 경로가 얼마든지 존재하지만, 최소의 거리로 갈 수 있는 방법은 이 방법 뿐이다.

 가중치는 가중치 인접 행렬이라고 불리는 2차원 배열에 저장된다. 가중치 인접 행렬은 기존의 인접행렬과 차이점이 있다. 기존의 인접 행렬에서는 간선이 없는 구간에는 행렬의 값을 0으로 했었다. 그러나 가중치 인접 행렬에서는 간선의 가중치 자체가 0일 수도 있기 때문에 간선이 없음을 나타낼 때 0이라는 값을 사용할 수가 없다.

 따라서 0 대신 이론적으로 무한대의 값을 가중치 인접 행렬에 저장함으로써 간선이 없다고 표시할 수 있는데, 컴퓨터에서는 무한대를 구현할 수 없으므로 다른 방법을 생각해야 한다. 따라서 실제 구현에서 만약 간선이 존재하지 않으면 정수 중에서 상당히 큰 값을 무한대라고 생각하기로 하고 가중치 인접 행렬에 저장하는 것으로 구현한다. 위 그래프의 가중치 인접 행렬을 나타내자면 아래와 같이 나타낼 수 있다.

# Dijkstra의 최단 경로 알고리즘

---

Dijkstra의 최단 경로 알고리즘은 네트워크에서 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘이다. 최단 경로는 경로의 길이순으로 정해진다. Dijkstra의 알고리즘에서는 시작 정점에서 집합 S에 있는 정점만을 거쳐서 다른 정점으로 가는 최단 거리를 기록하는 배열이 반드시 있어야 한다. // 집합 S에는 최단 거리에 해당하는 정점이 하나씩 추가될 예정이다.

 최단 거리를 기록하는 1차원 배열을 하나 설정하고 이름을 distance로 한다. 시작 정점을 v라고 했을 때, distance[v] = 0 이고 다른 정점에 대한 distance 값은 시작 정점과 해당 정점 간의 가중치가 된다. 가중치는 인접 행렬에 저장되므로 가중치 인접 행렬을 weight라 했을 때 distacne[w] = weight[v][w] 과 같이 사용할 수 있다.

 단, 정점 v에서 정점 w로의 직접 간선이 없을 경우에는 무한대의 값을 저장한다. 시작 단계에서는 아직 최단 경로를 발견하지 못했으므로 S = { v } 와 같을 것이다. 즉 처음에는 시작 정점 v를 제외하고는 최단거리가 알려진 정점이 없다. 알고리즘이 진행되면서 최단 거리가 발견되는 정점들이 S에 하나씩 추가될 것이다.

 알고리즘의 매 단계에서 집합 S 안에 있지 않은 정점 중에서 가장 distance 값이 작은 정점을 S에 추가한다. 새로운 정점 u가 S에 추가되면, S에 있지 않은 다른 정점들의 distance 값을 수정한다. 시작 기준점이 u로 바뀌었기 때문에, 새로 추가된 정점 u를 거쳐서 정점까지 가는 거리와 기존의 거리를 비교한다. 그 후 더 작은 거리값을 기준으로 distance값을 수정한다. 아래와 같은 수식을 이용하면 될 것이다.

 distance[w] = min(distance[w], distance[u] + weight[u][w]) // min은 stdlib.h에 선언되어 있는 매크로다. 매개 변수로 들어온 두 값중 더 작은 값을 리턴한다.

  아래의 예제 그래프를 통해 Dijkstra 알고리즘이 어떻게 진행되는지, 그리고 집합 S와 distance 배열은 어떻게 값이 바뀌어가는지 그 과정을 살펴보자. 시작 정점을 0으로 잡았다고 생각하고 흐름을 따라가 보자.

 시작 정점을 0으로 잡고, 각 지점까지의 거리를 표시했다. 직접적으로 가는 경로가 없는 경우 무한대로 표시되어 있다. 표시 되어 있는 거리 중 가장 짧은 거리는 정점 4까지의 거리인 3이므로 정점 4를 집합 S에 추가시켜준다.

 새로운 정점이 S에 추가되면 다른 정점들의 distance 값이 변경된다. 0번 정점에서는 직접적으로 갈 수 없던 정점에 새롭게 들어온 정점 4를 통해 직접적으로 갈 수 있기 때문에 무한대의 값에서 구체적인 정수거리로 정보가 갱신됐다. // 정보를 갱신할 때는 4번 정점을 기준으로 하고 있으므로, 4번 정점까지의 거리는 기본옵션으로 더해주는 것이 맞다. 즉, 4번 정점에서 뻗어나가는 각 정점에 3을 더해서 distance 배열에 넣어야 한다는 뜻이다.

 또한 새로운 정점 4를 통해 갈 때 더 짧은 경로가 발견 된다면 그 정보 또한 갱신을 해준다. 구체적으로는 위의 0번 정점만을 선택했을 때, 1번 정점까지의 거리가 7이였는데, 4번 정점을 택함으로써 이 거리가 5로 줄어들었다. 즉 더 짧은 거리가 나타나거나 기존의 무한대에서 직접 경로가 생겼을 때 거리(비용) 값을 갱신해준다.

 갱신된 정보들을 바탕으로 집합 S에 추가할 다음 정점을 선택해보자. 남은 정점 중 가중치가 가장 적게 표시되어 있는 건 정점 1이다. 1번 정점을 집합 S에 추가하고, 갱신할 수 있는 정보가 있다면 갱신해주자.

 

 갱신된 정보는 2번 정점에 대한 가중치다. 1번 정점을 추가함으로써 2번 정점까지 직접적으로 갈 수 있게 되었으므로 무한대의 값에서 구체적인 가중치인 9로 수정해준다. 다음으로, 현재까지의 distance 배열값을 기준으로 가장 작은 값은 6번 정점의 8이므로, 6번 정점을 택한다. 마찬가지로 갱신할 수 있는 정보는 갱신해준다.

 6번 정점을 집합 S에 추가함으로써 갱신할 수 있는 정보는 정점 3까지의 거리다. 기존의 14에서 12로 거리가 단축되었으므로, 이 값을 갱신했다. 이제 다음에 택할 정점을 생각해보자. distance 배열에서 가장 작은 가중치는 9이므로 정점 2를 택한다.

 정점 2를 집합 S에 추가함으로써 정점 3까지의 거리가 갱신되었다. 남은 두 개의 과정은 그림을 올리지 않아도 유추가 가능하다. 가중치가 가장 적은 5번 정점을 선택하고, 갱신할 정보가 있다면 갱신한다. 그 다음은 마지막 정점인 3번 정점을 택한다. 다익스트라 알고리즘은 위와 같은 순서와 원리로 진행 된다.

# Dijkstra 알고리즘을 구현한 프로그램

---

 위에서 우리가 쭈욱 살펴봤던 과정들을 프로그램으로 정리했다. weight 2차원 인접 행렬에 저장되어 있는 그래프의 정보는 위에서 설명한 그래프와 동일하다. 현재까지 나온 정점의 가중치 중 최소 가중치를 갖는 정점의 위치를 반환하는 choose 알고리즘과 choose를 사용한 이후 정보갱신을 하는 shortest_path 함수를 집중적으로 살펴보자.

/*************************************************
 ** 다익스트라 최단 경로 프로그램
*************************************************/

#include <stdio.h>

#define INT_MAX 2147483647 // 최대 정수
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 7	// 정점의 수
#define INF 1000		// 무한대 (연결이 없는 경우)

int weight[MAX_VERTICES][MAX_VERTICES] = {
	{0,7,INF,INF,3,10,INF},
	{7,0,4,10,2,6,INF},
	{INF,4,0,2,INF,INF,INF},
	{INF,10,2,0,11,9,4},
	{3,2,INF,11,0,INF,5},
	{10,6,INF,9,INF,0,INF},
	{INF,INF,INF,4,5,INF,0}
};

int distance[MAX_VERTICES];	// 시작 정점으로부터의 최단 경로 거리
int found[MAX_VERTICES];	// 방문한 정점 표시

int choose(int distance[], int n, int found[])
{
	// 현재 distance 배열에서 가장 작은 가중치 값이 위치하고 있는
	// 배열의 인덱스를 찾아 반환하는 함수

	int i, min, minpos;
	min = INT_MAX;
	minpos = -1;

	// 최소값 min을 찾는 반복문이다.
	// 방문한 적이 없는 정점에 대해 distance배열의 값들을 비교한다.
	for (i = 0; i < n; i++)
	{
		// 방문된 적이 없는 정점이고 현재까지의 최소값 min 보다 작다면
		if (distance[i] < min && found[i] == FALSE)
		{
			// 최소값을 의미하는 min 정보를 갱신해준다.
			min = distance[i];

			// 최소값이 등장한 해당 정점의 인덱스를 minpos에 저장한다.
			minpos = i;
		}
	}
	// distnace 배열에서 최소값이 위치하고 있는 인덱스를 반환한다.
	return minpos;
}

void shortest_path(int start, int n)
// start 정점부터 n 정점까지의 최단 경로를 찾는 알고리즘
{
	int i, u, w;

	/* 초기화 작업 */
	for (i = 0; i < n; i++)
	{
		// 시작 정점 start를 기준으로 했을 때의 가중치로
		// distance 배열을 초기화 한다.
		distance[i] = weight[start][i];

		// 아직 시작을 안했으므로 방문 표시의 역할을 하는 
		// found 배열을 FALSE로 초기화 한다.
		found[i] = FALSE;
	}
	// 시작 정점을 선택했으니 방문여부를 TRUE로 설정한다.
	found[start] = TRUE;
	distance[start] = TRUE;

	for (i = 0; i < n - 1; i++) // 위에서 시작 정점 값을 설정했으므로 여기서는 하나를 뺀 만큼만 반복한다.
	{
		// 최소값이 있는 인덱스의 정보를 u에 저장한다.
		u = choose(distance, n, found);

		// 현재 distance 배열에서 가장 작은 값이 위치한 인덱스는 u이므로
		// u번 정점을 선택을 한다. 선택함과 동시에 TRUE로 값을 써주며 방문 표시를 한다.
		found[u] = TRUE;

		// 최소 가중치가 있는 정점을 집합 S에 추가한 뒤 우리는 갱신할 수 있는 정보가 있다면
		// 그 정보를 갱신해준다. 무한대 (이 PG에서는 1000)에서 정수 거리로 갱신되는 정보나
		// 긴 거리에서 짧은 거리로 갱신되는 정보나 아래의 로직이 그대로 작동한다.
		for (w = 0; w < n; w++)
		{
			// 아직 선택되어 지지 않은 정점이고
			if (found[w] == FALSE)
			{
				// 현재 그 정점까지의 거리 (distance[u]) + 정점 w까지의 거리가
				// 기존의 w정점까지의 거리보다 가깝다면 그 정보를 갱신해준다.
				if (distance[u] + weight[u][w] < distance[w])
				{
					distance[w] = distance[u] + weight[u][w];
				}
			}
		}
	}
}

void main()
{
	shortest_path(0, MAX_VERTICES);
}
/*************************************************
 ** End Line
*************************************************/

위 프로그램의 효율성을 높이기 위해서는 최소값을 선택해서 그 위치를 반환하는 choose 함수를 우선순위 큐로 대치하여 속도를 높이는 방법이 있다. 우선순위 큐를 쓰면 단지 pop으로 최소값을 빼내면 되는 것이므로, choose 함수 내의 for문이 필요가 없어지기 때문이다. 그만큼 속도 향상을 기대할 수 있다.

 시간복잡도의 경우, $n$개의 정점이 있다고 했을 때 Dijkstra 최단 경로 알고리즘은 주 반복문을 $n$번 반복하고 내부 반복문을 $2n$번 반복하므로 $O(n^2)$의 시간복잡도를 가진다.