[알고리즘] C++로 다익스트라 알고리즘 구현하기

1. 다익스트라 알고리즘이란?

알고리즘을 공부하다보면 그래프를 공부하는 것이 굉장히 중요하다는 것을 자주 느낄 것이다.

그 중에서도 DFS, BFS와 더불어 가장 기초적이면서도 중요하게 생각되는 것이 최단경로 알고리즘일 것이고,

그 중에서도 다익스트라 알고리즘은 한 노드에서 다른 노드로의 최단 거리를 계산하는 중요한 알고리즘이다.

 

2. 간단하게 구현하기

소제목이 '간단하게 구현하기'인 만큼 문제가 있는 코드라고 생각할 지도 모르겠다.

실제로 아래와 같은 구현은 시간복잡도에서 조금은 '복잡한 구현' 보다 불리한 면이 있다.

하지만 다익스트라를 처음 공부할 때, 이해를 위해서 이와 같은 방법을 꼭 알고 있는 것이 좋다고 생각한다.

이것이 '간단하게 구현하기'인 이유는 3번에서 서술하겠다.

다른 알고리즘들이 그러하듯이, C++과 STL을 사용하면 다익스트라 알고리즘도 간단하게 구현할 수 있다.

다익스트라 알고리즘에서는 계산을 위해서 다음과 같은 배열이 필요한데, 벡터를 이용해서 간단히 구현 가능하다.

• d : 한 노드에서 다른 노드로의 최단 거리를 지속적으로 저장할 배열. 초기에는 무한대 값을 넣어준다.
• s : 어떤 노드로의 방문 여부를 저장하는 배열이다. 처음에는 모두 false로 초기화한다.
• graph : 2차원 배열 or 벡터 등으로 표현하며, 노드끼리의 인접 배열 / 리스트를 말한다.

우리의 코드에서는 벡터를 이용해서 모든 것을 구현할 것이고, 코드는 다음과 같이 심플하다.

#include <iostream>
#include <vector>

#define INF		214700000

using namespace std;

int V, E, K;
vector<vector<int>> graph;

vector<int> dijkstra()
{
	vector<bool> s(V, false);
	vector<int> d(V, INF);
	d[K - 1] = 0;

	while (1)
	{
		int m = INF, n;
		for (int i = 0; i < d.size(); i++)
		{
			if (s[i] == false && m > d[i])
			{
				m = d[i];
				n = i;
			}
		}
		if (m == INF) break;

		s[n] = true;

		for (int i = 0; i < d.size(); i++)
		{
			if (s[i] == true) continue;

			unsigned int via = graph[n][i] + m;
			if (d[i] > via) d[i] = via;
		}
	}

	return d;
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> V >> E;
	cin >> K;

	graph.assign(V, vector<int>(V, INF));

	while (E--)
	{
		int u, v, w;
		cin >> u >> v >> w;
		graph[u - 1][v - 1] = w;
		graph[v - 1][u - 1] = w;
	}

	vector<int> d = dijkstra();

	for (int i = 0; i < d.size(); i++)
	{
		if (d[i] == INF) cout << "INF" << '\n';
		else cout << d[i] << '\n';
	}

	return 0;
}

 

3. 완성도 있는 다익스트라 알고리즘

그렇다면 2번에서 구현한 알고리즘에 문제가 있는 부분은 무엇일까?

코드를 보면, d 배열의 값이 최소값이면서 방문하지 않은(즉, s[i]가 false인) 정점을 찾을 때 for문을 통해서 선형 검색을 하는 것을 알 수 있다. 이는 정점의 수가 많지 않을 때는 문제가 없지만, 실제 구현와 같은 경우에서는 정점의 수가

많아짐에 따라 선형 검색은 시간이 굉장히 많이 소요되기 때문에 문제가 있다고 할 수 있다.

이를 위해서 최소가 되는 정점을 찾을 때 시간복잡도를 O(log N)으로 획기적으로 줄일 수 있는 방법이 있는데,

이는 바로 우선순위 큐를 사용하는 방법이다.

코드는 다음과 같다.

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

#define INF		214700000

using namespace std;

typedef pair<int, int> P;
vector<vector<P>> graph;
int V, E, K;

vector<int> dijkstra()
{
	priority_queue<P, vector<P>, greater<P>> pq;
	vector<int> d(V, INF);
	d[K - 1] = 0;

	pq.push(P(0, K - 1));
	while (!pq.empty())
	{
		int node = pq.top().second;
		int weight = pq.top().first;
		pq.pop();

		// 방금 꺼낸 것이, 현재까지의 최소거리보다 큰 것이라면 무시하고 넘어간다.
		if(dist[node] < weight) continue;

		for (int i = 0; i < graph[node].size(); i++)
		{
			unsigned int via = d[node] + graph[node][i].first;
			if (via < d[graph[node][i].second]) {
				d[graph[node][i].second] = via;
				pq.push(P(via, graph[node][i].second));
			}
		}
	}

	return d;
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> V >> E >> K;
	graph.assign(V, vector<P>());

	while (E--)
	{
		int u, v, w;
		cin >> u >> v >> w;

		graph[u - 1].push_back(P(w, v - 1));
	}

	vector<int> d = dijkstra();

	for (int i = 0; i < d.size(); i++)
	{
		if (d[i] == INF) cout << "INF" << '\n';
		else cout << d[i] << '\n';
	}

	return 0;
}