Dijkstra's algorithm

목차 (클릭 시 이동)

 

Dijkstra's algorithm

 

 

 

 

 

 

 

 

 

 

 

 

Dijkstra 에 의해 1950년대 후반 출간된 이론으로, 그래프에서 정점들 간의 최단 거리를 계산하는 알고리즘이다. Dijkstra 는 네덜란드 출생으로 영미권을 제외하고 최초로 튜링상을 받았다.

 

Dijkstra 알고리즘은 현재 정점으로부터 인접한 간선들에 대해 edge relaxation 을 수행하고 그 시점에서 전체 정점들 중 가장 도달 비용이 적은 정점으로 이동해서 edge relaxation 하는 과정을 반복한다.

 

Bellman-Ford 알고리즘과 달리 도달 비용이 최소인 정점을 탐욕적으로 선택해 이동하며 edge relaxation 을 수행하기 때문에 더 빠른 시간에 최단 경로를 찾는다.

 

그렇다면 최소 비용의 정점으로 가는 것은 왜 최단 경로를 찾게 해 줄까? 직관적으로 생각해보면 합리적인 방법이다.

 

Dijkstra 알고리즘은 edge relaxation 을 진행한 모든 정점들을 우선 순위 큐에 저장하는데, 항상 그 중 최소 비용의 정점으로 간다.

 

만약 현재 정점까지 도달하는데 10 이 들었다고 하자, 규칙을 무시하고 그냥 현재의 인접 정점으로 이동한다면 다음 정점까지 도달 비용은 무조건 10 + a 이다.

 

그런데, 도달 비용이 7 인 정점이 큐에 있었고 해당 정점으로 이동해 edge relaxation 을 수행해 나가면 위의 규칙을 무시한 방법이 10 + a 로 도달했던 어떤 정점이 7 + a' 로 더 저렴하게 도달할 수 있는 여지가 생기는 것 이다.

 

따라서, Dijkstra 알고리즘이 방문하는 정점은 항상 최소 비용을 찾은 것 이고, 이를 다시 방문할 필요가 없기 때문에 최단 경로를 빠르게 찾는다.

코드 구현

이 알고리즘은 주어진 간선 정보대로 도달 비용을 갱신하는 Bellman-Ford 알고리즘과 달리 현재 정점의 인접 정점들을 갱신하기 때문에 주어지는 간선 정보를 통해 adjacency list 를 만들면 편하다.

 

int main() {
	vector<vector<int>> edges = {
		{1, 2, 5},
		{1, 4, 9},
		{1, 5, 1},
		{2, 3, 2},
		{2, 1, 5},
		{3, 2, 2},
		{3, 4, 6},
		{4, 3, 6},
		{4, 1, 9},
		{4, 5, 2},
		{5, 1, 1},
		{5, 4, 2}
	};

	int n = 5, s = 1; // n: number of vertices, s: start vertex
	vector<pair<int, int>> adj[n + 1];

	// It takes w weight from s to d
	for (auto& e: edges) {
		int s = e[0], d = e[1], w = e[2];
		adj[s].push_back({d, w});
	}
    ...

 

준비된 변수들로 알고리즘을 호출한다. 출발지인 s 로부터 거리 즉, 정답을 저장할 dist 배열과 최소 도달 비용의 정점을 가져올 우선 순위 큐를 선언한다.

 

vector<int> Dijkstra(int n, int s, const vector<pair<int, int>> adj[]) {
	vector<int> dist(n + 1, INF);
	priority_queue<pair<int, int>> cheapest;
	...

 

출발지인 s  의 도달 비용 (출발지이므로 0) 과 함께 큐에 push() 하며 BFS 구조의 작업을 시작한다.

 

	...
	dist[s] = 0;
	cheapest.push({0, s});

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

		if (dist[s] < cost) continue;
		...

 

큐의 top() 을 가져온다. 이는 큐의 원소 중 항상 최소의 도달 비용을 가진 원소를 의미한다. (비용은 push() 할 때 음수로 만들어 최소 비용으로 정렬. 따라서 가져올 때도 음수화해야 한다.)

 

그런데, 큐에서 가져온 정점의 도달 비용이 dist 배열에 저장된 비용보다 크다면 이미 최단 거리를 찾은 점인 것 이므로 더 이상 작업이 불필요하다.

 

큐에는 동일한 정점이 다른 도달 비용으로 여러번 push() 될 수 있다.  (이미 push() 된 정점에 대해 더 값싼 경로를 찾는 경우.)

 

이런 경우 더 값싼 경로가 먼저 pop() 되고 이 정점은 최소 도달 비용을 찾은 것이다.

 

나중에 더 비싼 경로 역시 pop()  되는데, dist 배열의 값 (이전에 찾은 최소 비용을 저장한 배열)과 비교해 더 큰 비용일 것이므로  작업을 건너뛰면 된다.

 

		...
		for (auto& e: adj[s]) {
			int d = e.first, w = e.second;

			// Push to pq only when it's updated
			if (dist[d] > dist[s] + w) {
				dist[d] = dist[s] + w;
				cheapest.push({-dist[d], d});
			}
		}
	}
	return dist;
}

 

edge relaxation 한 간선들 중 갱신이 일어난 간선에 대해서만 우선 순위 큐에 push() 한다.

 

갱신이 일어나지 않은 것은 이미 더 짧은 경로를 찾았다는 뜻이고, 그렇다면 이미 큐에 있거나 방문을 마치고 최소 비용을 찾은 정점이다.

 

전체 코드는 다음과 같다.

 

시간 복잡도

vector<int> Dijkstra(int n, int s, const vector<pair<int, int>> adj[]) {
	vector<int> dist(n + 1, INF);
	priority_queue<pair<int, int>> cheapest;

	dist[s] = 0;
	cheapest.push({0, s});
	...

 

본격적인 과정을 시작하기 전 거리 vector, 방문 vector 등을 선언하고 초기화 하는 과정이다. 정점의 개수 |V| 개 만큼 초기화 하므로 O(|V|) 의 시간 복잡도를 가진다. 

 

본격적인 알고리즘에 들어가면 Queue 에는 간선의 개수에 가까운 횟수의 push() / pop() 이 일어날 수 있다. (더 짧은 경로를 찾은 경우 이미 queue 에 포함된 정점이더라도 push() 된다.)

 

priority_queue 의 push() / pop() 동작은 heap 구조로 이루어져 N 개의 요소에 대해 logN 의 시간에 수행된다. 따라서, |E| 개의 간선에 대해 O(log|E|) 의 수행 시간을 가진다. ( push() 한 만큼 pop() 하므로 O(2*log|E|) = O(log|E|) )

 

Queue 의 top() 에서 얻은 정점에 대한 인접 정점의 edge relaxation 은 최대 간선의 개수 만큼 일어날 수 있다. 따라서, O(|E|) 의 시간 복잡도를 가진다.

 

이 그래프처럼 모든 간선이 출발 정점에 인접한 경우 위에서 설명한 worst case 를 충족한다.

 

	while (!cheapest.empty()) {
		int s = cheapest.top().second; cheapest.pop();

		for (auto& e: adj[s]) {
			int d = e.first, w = e.second;

			// Push to pq only when it's updated
			if (dist[d] > dist[s] + w) {
				dist[d] = dist[s] + w;
				cheapest.push({-dist[d], d});
			}
		}
	}

 

결국, 정점의 개수를 |V|, 간선의 개수를 |E| 라 할 때, 총 O(|V|) + O(|E| * log|E|) = O(|V| + |E|log|E|) 의 시간 복잡도를 가진다.