[알고리즘] 다익스트라 알고리즘(Dijikstra's Algorithm)

🔻다익스트라 알고리즘(Dijikstra's Algorithm)

 다익스트라 알고리즘이란 가중치 그래프에서 한 정점으로부터 모든 정점의 최단거리를 구하는 알고리즘이다. 다익스트라의 경우 가중치에 음수가 존재하면 안된다는 제약사항이 존재한다.

 

🔶다익스트라 알고리즘의 원리

 다익스트라 알고리즘의 기본적인 원리는 굉장히 간단하다. 두가지 작업을 모든 정점을 모두 방문할 때까지 반복하는 것이다.

1. 방문하지 않은 정점 중 가장 cost가 작은 정점을 방문한다.
2. 해당 정점과 연결된 정정들 중에서 거리가 이전에 기록한 값보다 작다면 값을 갱신한다

이 두작업을 무한 반복하는 것인데, 글로만 보면 무슨 말인지 이해하기 힘들 수 있으니 그림을 통해 알아보자.

 

6개의 정점이 있고 각 정점사이의 cost가 그림과 같은 그래프에서 0번 정점에 대해서 모든 정점의 최단거리를 구하는 상황을 가정해보겠다.

최단거리를 저장하는 배열의 값을 모두 무한대의 값으로 설정하고 0번에 대해서는 자기 자신이므로 0으로 설정해준다.

먼저, 0번 정점을 방문하여 그와 연결된 1, 3번 정점의 거리를 구한다. 맨처음 계산이라 무조건 해당 거리가 최단거리값이 되겠지만, 알고리즘에 의해 설명을 하면 최단 거리를 저장하는 배열을 bset라고 하면

best[1] 과 best[0] + (0과 1사이의 거리)를 비교하여 작은값을 best[1]에 넣는다. 무한대 값과 15를 비교하면 15가 작으므로 15가 best[1]에 들어가게 되는것이다.

같은 방법으로 3번정점과의 거리도 구하여 최단거리를 갱신한다.

 그렇게 인접정점의 거리를 구하면 다음 정점을 방문하는데, 가장 작은 값을 얻은 1번 정점을 우선으로 방문한다.

위와 같은 방법으로 1번에 대해서 인접 정점과의 거리를 계산하는데 (0으로부터 1번의 최단거리) + 2번의 거리를 best에 있는 값과 비교하여 작은 값을 넣는다.

 3번 정점에 대해서도  (0으로부터 1번의 최단거리) + (1번과 3번의 거리) = 25이고 현재 best에 들어가있는 값은 1번에서 3번으로 바로가는 거리인 35인데 알고리즘을 통해서 1번에서 3번으로 바로가는 것보다 1번을 거쳐서 3번으로 가는 방법이 더 짧다는 것이 밝혀졌으므로 최단거리를 15 + 10인 25로 갱신시켜준다.

 

다음 2번정점을 방문하게 되는데 2번정점은 연결된 인접정점이 없으므로 넘어간다.

바로 다음 3번정점으로 넘어가서 4번정점과의 거리를 구한다.

(0에서 3번으로가는 최단거리) + (3에서 4로 가는 거리) = 30 < best[4] = INF 이므로 best[4]는 30으로 갱신된다.

5번 정점은 0번으로부터 갈방법이 없으므로 무한대값으로 그대로 가고 갈수 있는 모든 정점을 방문하였으므로 알고리즘이 끝나게 된다. 알고리즘이 끝나게 되면 0번으로부터 각 정점으로 가는 최단거리가 모두 구해진 것을 볼 수 있다.

 그림으로 보니깐 훨씬 간단하다. 

방문할 정점을 정해주고(우선순위는 cost가 적은 정점우선), 현재 정점을 i, 방문한 정점은 j라고 하면 

best[i] + distance[i->j] 와 best[j]중 작은 값을 최단거리로 갱신 해주는 것이다.

더 간단하게 표현해보자면 min(best[i] + distance[i->j],  best[j])로 쓸 수 있겠다.

 

 

🔶다익스트라 알고리즘의 구현

 기본적인 원리를 알았으므로 코드로 구현해보도록 하자. C++코드로 작성되었다.

void Dijikstra(int here, int size)
{
	struct VertexCost
	{
		int vertex;
		int cost;
	};
	
	list<VertexCost> discoverd;
	vector<int> best(size, INT32_MAX);
	vector<int> parent(size, -1);
	
	discoverd.push_back(VertexCost{ here, 0 });
	best[here] = 0;
	parent[here] = here;

	while (!discoverd.empty())
	{
		list<VertexCost>::iterator bestIt;
		int bestCost = INT32_MAX;

		for (auto it = discoverd.begin(); it != discoverd.end(); ++it)
		{
			if (it->cost < bestCost)
			{
				bestCost = it->cost;
				bestIt = it;
			}
		}

		int cost = bestIt->cost;
		here = bestIt->vertex;
		discoverd.erase(bestIt);

		if (best[here] < cost)
			continue;

		for (int there = 0; there < size; there++)
		{
			if (adjacent[here][there] == -1)
				continue;

			int nextCost = best[here] + adjacent[here][there];
			if (nextCost >= best[there])
				continue;

			discoverd.push_back(VertexCost{ there, nextCost });
			best[there] = nextCost;
			parent[there] = here;
		}
	}
}

전체적인 코드는 이렇고 하나씩 살펴보도록하자.

struct VertexCost
{
	int vertex;
	int cost;
};
	
list<VertexCost> discoverd;
vector<int> best(size, INT32_MAX);
vector<int> parent(size, -1);
	
discoverd.push_back(VertexCost{ here, 0 });
best[here] = 0;
parent[here] = here;

먼저 처음 정점을 지정해주는 작업이다. 최단거리를 나타내는 배열인 best의 값을 모두 무한대의 값으로 설정해주고, 방문할 정점의 목록인 discoverd라는 list도 만들어준다. 그리고 맨처음 시작정점을 방문목록에 넣어주면서 알고리즘이 시작된다.

 

while (!discoverd.empty())
{
	list<VertexCost>::iterator bestIt;
	int bestCost = INT32_MAX;

	for (auto it = discoverd.begin(); it != discoverd.end(); ++it)
	{
		if (it->cost < bestCost)
		{
			bestCost = it->cost;
			bestIt = it;
		}
	}

	int cost = bestIt->cost;
	here = bestIt->vertex;
	discoverd.erase(bestIt);

	if (best[here] < cost)
		continue;

	for (int there = 0; there < size; there++)
	{
		if (adjacent[here][there] == -1)
			continue;

		int nextCost = best[here] + adjacent[here][there];
		if (nextCost >= best[there])
			continue;

		discoverd.push_back(VertexCost{ there, nextCost });
		best[there] = nextCost;
		parent[there] = here;
	}
}

실직적으로 알고리즘이 수행되는 부분인데, 이 부분도, 다음 방문할 정점을 고르는 작업, 정점에서 연결된 정점들의 거리를 구하는 작업 두가지로 찢어서 보도록하겟다.

list<VertexCost>::iterator bestIt;
int bestCost = INT32_MAX;

for (auto it = discoverd.begin(); it != discoverd.end(); ++it)
{
	if (it->cost < bestCost)
	{
		bestCost = it->cost;
		bestIt = it;
	}
}

int cost = bestIt->cost;
here = bestIt->vertex;
discoverd.erase(bestIt);

if (best[here] < cost)
	continue;

먼저 방문할 정점을 고르는 부분이다. 최단거리를 구할 때마다, 방문목록에 그 정보를 넣어주게되는데 그중에서 cost값이 가장 작은 정점을 찾아서 골라준다. 그리고 고른 정점은 방문목록에서 삭제해주고 이제 이 고른정점에 연결된 정점에대한 최단거리를 구하는 일을 수행할 것이다.

if (best[here] < cost)
	continue;

 이 코드를 넣은이유는 더 짧은 경로를 찾았다면 코드의 무한반복이나 비효율적인 작업을 피하기위해 넣은 코드인데, 예를 들자면 위에 그림에서 0 ->3으로 가는 거리인 35가 맨처음 방문목록에 들어왔는데, 뒤늦게 0에서 1을 거쳐 3으로 가는 것이 더 짧다는 것이 밝혀지고, 0 -> 3으로 가는 거리 25가 또 방문목록에 들어오게 된다. 그러면 저 작은 코스트를 먼저 방문하므로 (3, 35)짜리는 계속에서 리스트에 남아있다가 마지막에 실행이 될텐데, 이미 3번에 대해서 계산이 끝났는데 똑같은 작업을 또 수행하게 되고 무한반복을 하게된다. 그래서 저코드를 넣어서 중복된 값중에 코스트가 큰값은 그냥 날려주는 것이다. 말로하면 이해가 잘안될 수 있는데 저 코드를 빼고 한번 실행해보면 무슨 말인지 알 수 있을 것이다.

 

for (int there = 0; there < size; there++)
{
	if (adjacent[here][there] == -1)
		continue;

	int nextCost = best[here] + adjacent[here][there];
	if (nextCost >= best[there])
		continue;

	discoverd.push_back(VertexCost{ there, nextCost });
	best[there] = nextCost;
	parent[there] = here;
}

그러면 마지막으로 방문할 정점을 골랐으면 그 정점에 대해서 연결된 정점의 최단거리를 구하는 작업을 수행하는데,

MIN(best[there] , best[here] + adjacent[here][there])과 같은 작업을 수행하여 그값을 갱신하고 갱신이 되었다면, 해당 정점을 방문목록에 넣어주게 된다.

 

🔶시간복잡도

 위의 구현한 코드는 방문목록을 담는 자료구조로 list를 선택하였다.

그렇게되면 방문할 정점를 탐색하는데 최악의 경우 O(V)

해당 정점에서 주변 노드들의 거리를 계산하여 최단거리를 갱신하는 과정이 O(V)

인데 O(V) + O(V) = O(V)이고 이를 V번 반복하므로 O(V^2)이 된다.

따라서 배열을 통하여 구현하였을 경우 시간복잡도는 O(V^2)이다.

하지만 방문목록을 담는 자료구조를 우선순위큐를 사용하면 시간복잡도를 줄일 수 있는데, 이부분에 대해서는 우선순위큐를 먼저 정리하고 다시 포스팅 해보도록하겠다.

 

🔻마치며

다익스트라 알고리즘의 경우 맨처음에 공부를 할때는 되게 어려운 알고리즘인줄 알았는데 막상 하나하나씩 스텝을 따라가보며 공부해보니 생각보다 굉장히 간단한 알고리즘이었다. 또한 활용방안도 굉장히 많은 알고리즘인 것 같아서 확실하게 새겨두기위해 정리해 보았다. 우선순위큐를 통한 구현에 대해서는 더 공부해서 정리해보는 시간을 가져야할 것같다.