'알고리즘/최단거리'에 해당되는 글 1건

다익스트라 알고리즘 (Dijkstra Algorithm)

최단거리를 구하는 데에는 꽤 여러가지 알고리즘이 존재합니다. 그 중에서 가장 유명한 알고리즘, 다익스트라 알고리즘에 대해서 알아보도록 하겠습니다.

다익스트라 알고리즘은 무엇일까요?

그래프의 한 정점에서 모든 정점까지의 최단 거리를 구하는 것이 이 알고리즘입니다. 

우선 아래와 같은 그래프가 있다고 가정해볼게요.

정점 0에서 모든 정점까지의 최단거리는 어떻게 될까요?

0번에서부터 5번 정점 중 임의의 i까지 최단 거리를 dist[i]라고 할때

가 됩니다.

이와 같이 어떤 시작점을 정해서 그 정점부터 다른 정점까지의 최단거리를 구하는 알고리즘이 바로 단일 시작점 알고리즘이고, 대표적인 알고리즘이 바로 다익스트라 알고리즘입니다.

BFS 최단거리 기반

이 알고리즘은 최단 거리를 구하는 것이기 때문에 BFS를 기반으로 움직이는데요. BFS는 자료구조에서 큐를 썼었죠? 따라서 다익스트라 알고리즘 역시 큐를 사용하여 구현할 수 있다는 사실을 알아두세요.

주의 사항은 위의 그래프가 나타내는 것처럼 음수간선이 있으면 다익스트라 알고리즘을 쓸 수가 없어요.

다익스트라 구현 (C++)

코드로 다익스트라 알고리즘을 살펴본 후 설명하도록 하겠습니다.

#include <vector>
#include <iostream>
#include <queue>

#define MAX_V 100
#define INF 99999999
using namespace std;


vector<pair<int, int> > adj[100];
vector<int> dijkstra(int start, int V) {
	vector<int> dist(V, INF);
	dist[start] = 0;
	priority_queue<pair<int, int> > q;
	q.push(make_pair(0, start));

	while (!q.empty()) {
		int cost = -q.top().first;
		int from = q.top().second;
		q.pop();

		if (dist[from] < cost) continue;

		for (int i = 0; i < adj[from].size(); i++) {
			int to = adj[from][i].first;
			int distFromTo = cost + adj[from][i].second;
			if (distFromTo < dist[to] ) {
				dist[to] = distFromTo;
				q.push(make_pair(-distFromTo, to));
			}
		}
	}
	return dist;
}

int main(int argc, char **argv)
{
	int E, V;
	printf("[input] vertex edge :");
	scanf("%d %d", &V, &E);

	
	for (int i = 0; i < E; i++) {
		printf("[input] from to cost :");
		int from, to, cost;
		scanf("%d %d %d", &from, &to, &cost);
		adj[from].push_back(make_pair(to, cost));
		adj[to].push_back(make_pair(from, cost));
	}

	printf("===dijkstra===\n");
	vector<int> dist = dijkstra(0, V);
	for (int i = 0; i < V; i++) {
		printf("from 0 to %d : %d\n", i, dist[i]);
	}
	return 0;
}

우선 입력을 받습니다. 위의 그래프 모양 그대로 입력을 받습니다. 위의 그래프를 조금 더 편하게 입력받으려면 아래의 input을 복사해서 붙여넣으세요.

이후 dijkstra가 어떻게 동작하는 지 그림을 보며 살펴보도록 합시다.

우선 우리가 반환한 dist의 벡터 사이즈를 V의 크기(정점의 개수)로 정하고 그 값을 아주 큰 값으로 설정합니다.

자기 자신과의 거리는 0이므로 dist[start]는 0으로 셋팅합니다.

여기서는 priority queue를 사용하는데요. 그 이유는 정점으로부터 가장 작은 값으로 연결되어 있는 정점을 꺼내는 것이 더 효율적이니까 그렇습니다.

또한 priority queue는 pair를 통해서 우선 순위를 정할때 첫번째 요소를 기준으로 가장 큰 값을 먼저 꺼내옵니다. 그래서 첫번째 요소를 거리, 그것도 -를 붙여서 넣어주면 값이 큰 간선으로 연결된 정점이 더 나중에 나오게 되는 것이죠.

그래서 꺼내올때 -를 붙여서 꺼내오고 -를 붙여서 집어 넣습니다.

이제 그림으로 더 쉽게 보도록 합시다.

우선 초기상태는 자기 자신의 정점을 우선순위 큐에 push하며 그 거리는 0이 됩니다. while루프를 돌기 전의 모습입니다. 

그 후 첫 while 루프를 돌면서 큐에 저장된 (0,0)을 가져옵니다. 0은 dist[0]보다 작지 않기 때문에 if문에 걸리지 않고 for루프를 돌게 됩니다. 주변에 가장 작은 값으로 연결된 정점은 2, 1, 3이지요. 그래서 그에 대응되는 거리 2, 3, 5와 함께 우선 순위 큐에 저장합니다. 

하지만 우선순위 큐는 큰 값이 먼저 선정되기 때문에 음수를 붙여서 -2,-3,-5로 바꾸어서 넣어줍니다.

** 아래 그림에서 잘못된 것이 있는데 우선순위 큐에 푸시되는 값은 (-2,2) (-3,1) (-5,3)인것으로 정정해주세요. 죄송해요.

우선순위 큐에서 2를 꺼내올때 이미 dist[2]는 2로, dist[2]보다 2가 더 작지 않으므로 if 조건문에 걸려 continue됩니다.

이 후 (-3, 1)을 꺼내옵니다. 정점 1에서 연결된 정점 중 가장 가까운 정점은 4입니다. 그렇기 때문에 dist[4]를 12로 수정하고 이 정보를 우선순위 큐에 저장합니다.

이제 (-5,3)을 꺼내올 차례이군요. dist[3]은 5이고, 큐에서 꺼내온 값 역시 5이므로 if문에 걸리지 않고 for루프를 돕니다. 이제 3에 연결되어 있는 정점은 4로 연결된 cost가 1인 간선입니다. 그래서 그전에 있던 dist[3]과 4로 연결된 간선의 cost 1을 더한 값(6)과 dist[4]와 연결된 값과 비교해보니 6이 더 작으므로 dist[4]=6으로 갱신하고 (-6,4)를 큐에 집어 넣습니다.

여기서 우선순위 큐를 사용하는 이유가 나옵니다. 만일 순서를 고려하지 않고 (-5, 3)이 큐에 맨 끝에 위치해있다면 이러한 갱신을 맨끝에 하게 되어 for루프를 돌게 되는 시간적인 낭비가 있게 되는 겁니다. 

그렇기 때문에 가장 비용이 낮은 것이 먼저 나오는 것이 유리하다는 것이죠.

다음 (-15,4)는 cost가 15이기 때문에 if조건에 걸려 continue됩니다. 

남은 (-6, 4)를 꺼내오게 되면 if조건문에 걸리지 않고 for루프를 돌아요. 4와 연결된 정점 5까지의 비용은 dist[4]와 3을 더한 9가 됩니다. 왜냐하면 dist[5]는 아주 큰 값이기 때문에 6이 더 작잖아요?

그 후 5와 연결된 간선의 정보를 큐에 저장합니다.

이제 마지막 (-9, 5)를 꺼내오는데, 이미 dist[5]=9이므로 if 조건에 걸려 continue됩니다. 이 후에는 큐가 비었으므로 while문을 탈출하게 되지요.

이제 모든 거리를 구했습니다.

코드에서는 0을 기준으로 구했는데 코드를 바꾸어서 1부터 시작해서 최단거리를 구해보세요. 그리고 비교해보세요.