다익스트라 알고리즘

다익스트라 알고리즘

그래프에서 최단 거리를 구하는 알고리즘

• 기능 : 출발 노드와 모든 노드 간의 최단 거리 탐색
• 특징 : 에지는 모두 양수
• 시간 복잡도 : O(ElogV)

특정 노드에서 다른 노드들의 최단 거리를 구하는 문제가 주어졌을 때 다익스트라 알고리즘을 사용하면 문제를 해결할 수 있다.

 

 

다익스트라는 출발 노드와 이외의 모든 노드 간의 최단 거리를 표현하는 알고리즘이다.

 

3단계의 값이 가장 작은 노드 고르기는 우선순위 큐를 활용하면 된다.

 

백준 1753: 최단 경로

https://www.acmicpc.net/problem/1753

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

constexpr int MAX_VALUE = 10000000;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int V, E;
	cin >> V >> E;
	vector<vector<pair<int, int>>> graph(V + 1);
	vector<bool> visited(V + 1, false);
	vector<int> distance(V + 1, MAX_VALUE);

	int startV;
	cin >> startV;

	for (int i = 0; i < E; i++)
	{
		int s, e, w;
		cin >> s >> e >> w;
		graph[s].push_back(make_pair(e, w));
	}

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;
	Q.push(make_pair(0, startV));
	distance[startV] = 0;

	//다익스트라
	while (!Q.empty())
	{
		auto cur = Q.top();
		Q.pop();

		int curNode = cur.second;

		//방문 체크
		if (visited[curNode])
		{
			continue;
		}
		visited[curNode] = true;

		//최소 거리 배열 업데이트 해주고, 다시 우선순위 큐에 삽입
		for (auto node : graph[curNode])
		{
			if (distance[node.first] > distance[curNode] + node.second)
			{
				distance[node.first] = distance[curNode] + node.second;
				Q.push(make_pair(distance[node.first], node.first));
			}
		}
	}

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

	return 0;
}

 

처음에 풀었을 때, 우선순위 큐를 사용하지 않아서 시간 초과가 났다.

두 번째 시도에서는 무한대 값을 INT32_MAX로 했더니 오버플로가 나서 잘못된 값이 최단 거리로 들어갔다. 적당한 무한대 값을 넣어야 했다.

세 번째 시도에서는 INT16_MAX로 했는데, 틀렸다. 문제의 조건 범위를 고려하면 무한대로 INT16_MAX를 설정하는 것은 너무 작았다. 그래서 문제 범위를 고려해 무한대를 천만으로 잡았더니 정답이었다.

 

출발노드와 이외의 노드의 최단 거리를 구하고 간선이 양수라고 문제에서 말했기 때문에 다익스트라 알고리즘을 사용하면 되는 문제였다.

우선 순위 큐와 무한대 문제를 잘 숙지하도록 하자.

 

백준 1916 : 최소 비용 구하기

https://www.acmicpc.net/problem/1916

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

constexpr long long MAX_VALUE = 10000000000;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	long long V, E;
	cin >> V >> E;
	vector<vector<pair<long long, long long>>> graph(V + 1);
	vector<bool> visited(V + 1, false);
	vector<long long> distance(V + 1, MAX_VALUE);

	for (long long i = 0; i < E; i++)
	{
		long long s, e, w;
		cin >> s >> e >> w;
		graph[s].push_back(make_pair(e, w));
	}

	long long start, end;
	cin >> start >> end;

	priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> Q;
	Q.push(make_pair(0, start));
	distance[start] = 0;

	//다익스트라
	while (!Q.empty())
	{
		auto cur = Q.top();
		Q.pop();

		long long curNode = cur.second;

		//방문 체크
		if (visited[curNode])
		{
			continue;
		}
		visited[curNode] = true;

		//최소 거리 배열 업데이트 해주고, 다시 우선순위 큐에 삽입
		for (auto node : graph[curNode])
		{
			if (distance[node.first] > distance[curNode] + node.second)
			{
				distance[node.first] = distance[curNode] + node.second;
				Q.push(make_pair(distance[node.first], node.first));
			}
		}
	}

	cout << distance[end];

	return 0;
}

 

최단 거리를 구하고 간선이 양수이므로 다익스트라로 최단거리를 구하면 된다.

주의할 점은 무한대를 표현해야 하는데 가중치의 최대값이 10만이고 최대 간선 수가 10만 개이므로 100억으로 무한대를 잡아야 한다. 그러므로 long long 타입으로 가중치를 표현해야 한다.

 

백준 1854번 : K번째 최단 경로 찾기

https://www.acmicpc.net/problem/1854

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<vector<pair<int, int>>> graph;
priority_queue<int> distanceQ[1001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int V, E, K;
	cin >> V >> E >> K;
	graph.resize(V + 1);

	for (int i = 0; i < E; i++)
	{
		int s, e, w;
		cin >> s >> e >> w;
		graph[s].push_back(make_pair(e, w));
	}

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;
	Q.push(make_pair(0, 1));
	distanceQ[1].push(0);

	//다익스트라
	while (!Q.empty())
	{
		auto cur = Q.top();
		Q.pop();

		int w = cur.first;
		int curNode = cur.second;

		for (auto node : graph[curNode])
		{
			int nextNode = node.first;
			int weight = node.second;

			if (distanceQ[nextNode].size() < K)
			{
				distanceQ[nextNode].push(w + weight);
				Q.push(make_pair(w + weight, nextNode));
			}
			else if(distanceQ[nextNode].top() > w + weight)
			{
				distanceQ[nextNode].pop();
				distanceQ[nextNode].push(w + weight);
				Q.push(make_pair(w + weight, nextNode));
			}
		}
		
	}

	for (int i = 1; i <= V; i++)
	{
		if (distanceQ[i].size() == K)
		{
			cout << distanceQ[i].top() << '\n';
		}
		else
		{
			cout << -1 << '\n';
		}
	}
	return 0;
}

 

이 문제는 최단 거리가 아니라 K번째로 작은 거리를 구해야 한다. 가중치가 양수이므로 다익스트라를 사용할 수 있겠다.

 

K번째 거리를 구하기 위해서는 여러 아이디어들이 필요하다.

우선 K번째로 작은 거리를 구하려면 기본적인 다익스트라의 min(next 노드의 최단 거리,  현재 노드의 최단 거리 + next의 가중치) 이 부분을 잘 고치면 구할 수 있겠다 생각했다.

또, K번째 작은 거리를 구하기 위해서는 한 번 방문한 노드도 여러 번 방문할 수 있어야 한다.

그러므로 방문 체크하는 부분을 제거할 필요가 있다.

그리고 여러 거리들의 비용들을 관리해야 하므로 단순한 distance 배열이 아니라 우선순위 큐를 활용한 배열로 K 번째 거리까지는 데이터를 관리해야 한다는 사실을 알 수 있다.

 

이 문제는 혼자 풀기 어려워서 해설을 보고 이해한 후 직접 구현했다.

우선순위 큐를 잘 활용할 필요가 있겠다.

 

공부자료 : Do it! 코딩 테스트 알고리즘 C++ (김종관, 이지스퍼블리싱)