[Algorithm] Dijkstra

[Graph] Dijkstra

다익스트라 알고리즘은 음의 가중치가 없는 그래프에서 최단거리를 구하는 알고리즘이다.

초기에 다익스트라가 구현한 버전은 O(V^2)의 복잡도를 가진다.

원리는 아래와 같다.

1번 vertex에서 나머지 vertex까지의 최단 비용을 구한다고 가정하자.

1.먼저 현재 정점에서 가장 가까운 정점을 선택한다.
2.해당 정점을 방문했다고 표시한다.
3.해당 정점의 거리를 갱신한다.

여기서 3번 정점을 갱신하는 방법은 1번에서 선택된 정점으로 부터 갈수있는 정점 모두를 갱신한다.

인접행렬의 구현 O(V^2)

#include<iostream>
#include<vector>
using namespace std;
const int INF = 999999;
vector<int> dijkstra(vector<vector<int>>& v, int begin) {
	vector<int> d;
	vector<bool> visit;
	visit.assign(v.size(), false);	//모든 정점를 방문하지 않았다고 해야한다.
	d.assign(v.size(), INF);		//모든 거리를 무한대로 초기화한다.
	d[begin] = 0;					//시작정점 은 당연히 거리가 0이다.
	while(true){
		int min = INF;
		int s = -1;
		//방문하지 않은 정점중에 가장 비용이 적은 정점을 선택한다.
		//처음에는 시작 정점이 선택된다.
		for (size_t j = 1; j < v.size(); j++)
			if (visit[j] == false && min > d[j]){
				min = d[j];
				s = j;
			}
		//만일 선택된 정점이 없다면 종료한다.
		if (s == -1)break;	
		visit[s] = true;
		//찾은 정점에서 갈수있는 모든정점을 갱신한다.
		for (size_t j = 1; j < v.size(); j++)
			if (v[s][j]!=-1 && d[j]>d[s] + v[s][j])
				d[j] = d[s] + v[s][j];
	}
	return d;
}
int main() {
	vector<vector<int>> v;
	v.assign(7, vector<int>());
	for (auto& e : v)
		e.assign(7, -1);
	v[1][2]= 10 ;
	v[1][3]= 30 ;
	v[1][4]= 15 ;
	v[2][5]= 20 ;
	v[3][6]= 5 ;
	v[4][3]= 5 ;
	v[4][6]= 20 ;
	v[5][6]= 20 ;
	v[6][4]= 20 ;
	vector<int> d = dijkstra(v, 1);
	for (auto& e : d)
		cout << e << endl;
	return 0;
}

1번째 while 문은 반드시 V번 반복하고, 두번째 for문은 모든 정점을 확인해 보므로 V번 반복한다.
따라서 인접행렬의 경우 시간복잡도는 O(V^2) 다.

인접리스트의 구현 O(VE)

인접 리스트로 구현하면 다중 그래프에서도 다익스트라가 적용된다.

#include<iostream>
#include<vector>
using namespace std;
const int INF = 999999;
struct Edge{
	int to;
	int cost;
	Edge(int to, int cost) {
		this->to = to;
		this->cost = cost;
	}
};
vector<int> dijkstra(vector<vector<Edge>>& v, int begin) {
	vector<int> d;
	vector<bool> visit;
	visit.assign(v.size(), false);	//모든 정점를 방문하지 않았다고 해야한다.
	d.assign(v.size(), INF);		//모든 거리를 무한대로 초기화한다.
	d[begin] = 0;					//시작정점 은 당연히 거리가 0이다.
	while(true){
		int min = INF;
		int s = -1;
		//방문하지 않은 정점중에 가장 비용이 적은 정점을 선택한다.
		//처음에는 시작 정점이 선택된다.
		for (size_t j = 1; j < v.size(); j++)
			if (visit[j] == false && min > d[j]){
				min = d[j];
				s = j;
			}
		//만일 선택된 정점이 없다면 종료한다.
		if (s == -1)break;	
		visit[s] = true;
		//찾은 정점에서 갈수있는 모든정점을 갱신한다.
		//인접 리스트는 이반복문을 더 적게 돌 수 있다.
		for (size_t j = 0; j < v[s].size(); j++){
			if (d[v[s][j].to]>d[s] + v[s][j].cost)
				d[v[s][j].to] = d[s] + v[s][j].cost;
		}
	}
	return d;
}
int main() {
	vector<vector<Edge>> v;
	v.assign(7, vector<Edge>());
	v[1].push_back(Edge(2,10));
	v[1].push_back(Edge(3,30));
	v[1].push_back(Edge(4,15));
	v[2].push_back(Edge(5,20));
	v[3].push_back(Edge(6,5));
	v[4].push_back(Edge(3,5));
	v[4].push_back(Edge(6,20));
	v[5].push_back(Edge(6,20));
	v[6].push_back(Edge(4,20));
	vector<int> d = dijkstra(v, 1);
	for (auto& e : d){
		cout << e << endl;
	}
	return 0;
}

반면 인접리스트의 경우는 첫번째 while문은 V번 반복하고, 두번째 for문은 E번 반복하므로 시간 복잡도는 O(V*E) 가 된다.


이제 우선순위 큐를 이용하여 조금더 빠른 방법의 다익스트라를 알아보자.

위의 소스에서는 최소비용을 가진 정점을 찾는데 V의 복잡도가 필요했다.

그러나 최소정점을 찾는방식을 우선순위 큐를 사용하면 lgV 시간으로 해결이 가능하다.(삭제시간)

인접리스트 + 우선순위큐의 구현 O(ElgE)

#include<iostream>
#include<vector>
#include<queue>			//priority_queue
#include<functional>	//greater
using namespace std;
const int INF = 999999;
typedef pair<int, int> pii;
struct Edge{
	int to;
	int cost;
	Edge(int to, int cost) {
		this->to = to;
		this->cost = cost;
	}
};
vector<int> dijkstra(vector<vector<Edge>>& v, int begin) {
	vector<int> d;
	//<현재거리,정점> 최소힙을 구성
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	d.assign(v.size(), INF);		//모든 거리를 무한대로 초기화한다.
	d[begin] = 0;					//시작정점 은 당연히 거리가 0이다.
	pq.push(make_pair(0,begin));
	while (pq.empty()==false){
		pii e = pq.top();
		pq.pop();
		//선택된 최소비용의 정점의 모든 간선을 순회
		for (int i = 0; i < v[e.second].size(); i++){
			//만일 to의 거리가 현재거리+비용 보다 크다면 거리d 를 갱신
			if (d[v[e.second][i].to]> d[e.second] + v[e.second][i].cost){
				d[v[e.second][i].to] = d[e.second] + v[e.second][i].cost;
				//갱신된 거리와 해당정점을 우선순위큐에 push
				pq.push(make_pair(d[v[e.second][i].to], v[e.second][i].to));
			}
		}
	}
	return d;
}
int main() {
	vector<vector<Edge>> v;
	v.assign(7, vector<Edge>());

	v[1].push_back(Edge(2,10));
	v[1].push_back(Edge(3,30));
	v[1].push_back(Edge(4,15));
	v[2].push_back(Edge(5,20));
	v[3].push_back(Edge(6,5));
	v[4].push_back(Edge(3,5));
	v[4].push_back(Edge(6,20));
	v[5].push_back(Edge(6,20));
	v[6].push_back(Edge(4,20));

	vector<int> d = dijkstra(v, 1);
	for (auto& e : d){
		cout << e << endl;
	}
	return 0;
}

우선순위큐를 사용하게 되면 각정점마다 인접한 간선들을 모두 검사하는데 O(E)

우선순위 큐에 원소를 넣고 삭제하는데 걸리는 시간 O(lg V) (정점들이 우선순위 큐에 들어가므로)

그러나 거리d를 갱신할때 중복되에 큐에 들어갈 수 있다. 따라서 정점의 개수 V보다 좀더 우선순위 큐에 들어갈 수 있다.

이때 정점이 갱신되는것은 간선마다 한번씩 만 갱신되므로 최대 E번 우선순위 큐에 들어갈 수 있다.

우선순위큐의 삽입과 삭제를 고려하면 복잡도는 O(E lgE) 가 된다.

앞서말한 간선검사 시간과 합하면 Tn(E + ElgE) 이므로 O(ElgE) 가 된다.

명심하자, 우선순위큐를 사용하여 다익스트라를 구현하면 복잡도는 O(ElgE)가 된다.

그런데 보통 간선의 개수 E는 정점의 제곱 V^2 보다 작기 때문에 Tn(E 2lgV) 가되며 O(ElgV) 가 상한이 된다.

왜 정점들중에 최소값을 먼저 찾는가?

그 이유는 아래의 그래프를 보면 알 수 있다.

비용이 큰 정점부터 계산하게되면, 비용의 갱신이 더 많이 발생하기 때문이다.

비용의 갱신은 곧, 새로운 큐에 삽입하는것을 의미하기 때문에, 작은 비용인 정점부터 찾는것이다.

우선순위 큐의 단점. 중복

우선순위큐로 다익스트라를 구현하면, 중복된 정점이 삽입될 수 있다. 이때 기존의 정점은 제거를 해야하는데 우선순위큐의 자료구조 특성상 그럴수가 없다.

따라서 트리를 사용하게 되면 중복된 정점을 제거할 수 있어, 더 빠른 연산이 가능하다.

앞서 말한 큐에 정확하게 V의 개수가 삽입되기 때문에, 시간복잡도는 O(VlgV) 가 될 수 있다.

아래의 코드는 red/black을 기반을한 C++ std::set을 이용하여 다익스트라를 구현하였다.

인접리스트 + 레드블랙트리 구현 O(VlgV)

#include<iostream>
#include<vector>
#include<set>
#include<functional>	//greater
using namespace std;
const int INF = 999999;
typedef pair<int, int> pii;
struct Edge{
	int to;
	int cost;
	Edge(int to, int cost) {
		this->to = to;
		this->cost = cost;
	}
};
vector<int> dijkstra(vector<vector<Edge>>& v, int begin) {
	vector<int> d;
	set<pii> pq;					//삭제가 가능한 트리로 구성
	d.assign(v.size(), INF);		//모든 거리를 무한대로 초기화한다.
	d[begin] = 0;					//시작정점 은 당연히 거리가 0이다.
	pq.insert(make_pair(0,begin));
	while (pq.empty()==false){
		pii e = *pq.begin();	//트리의 제일 작은값을 가져옴
		pq.erase(e);
		//선택된 최소비용의 정점의 모든 간선을 순회
		for (int i = 0; i < v[e.second].size(); i++){
			//만일 to의 거리가 현재거리+비용 보다 크다면 거리d 를 갱신
			if (d[v[e.second][i].to]> d[e.second] + v[e.second][i].cost){
				//기존 정점을 제거하고 더 비용이낮은 정점으로 교체
				pq.erase(make_pair(d[v[e.second][i].to], v[e.second][i].to));
				d[v[e.second][i].to] = d[e.second] + v[e.second][i].cost;
				pq.insert(make_pair(d[v[e.second][i].to], v[e.second][i].to));
			}
		}
	}
	return d;
}
int main() {
	vector<vector<Edge>> v;
	v.assign(7, vector<Edge>());
	
	v[1].push_back(Edge(2,10));
	v[1].push_back(Edge(3,30));
	v[1].push_back(Edge(4,15));
	v[2].push_back(Edge(5,20));
	v[3].push_back(Edge(6,5));
	v[4].push_back(Edge(3,5));
	v[4].push_back(Edge(6,20));
	v[5].push_back(Edge(6,20));
	v[6].push_back(Edge(4,20));
	
	vector<int> d = dijkstra(v, 1);
	for (auto& e : d){
		cout << e << endl;
	}
	return 0;
}