VennTum's profile image

VennTum

April 18, 2021 01:00

Shortest Path Algorithm - Dijkstra

data-structure , algorithm

Dijkstra

다익스트라 알고리즘은 그래프에서 한 정점(시작 정점)에서부터 다른 모든 정점으로의 최단경로를 구하는 알고리즘입니다. 여기서 최단경로란, 정점과 정점 사이를 잇는 간선이 가중치를 가지고 있을 때, 한 정점에서 다른 정점으로 간선을 타고 이동할 수 있는 경로중 가중치의 합이 가장 작은 경로를 말합니다. 다익스트라는 한 정점으로부터 다른 정점으로의 최단경로와 그 과정에서 거치는 간선들의 가중치 합을 알아낼 수 있습니다.

다익스트라는 알고리즘의 구조 상 다음과 같은 성질들을 가지게 됩니다.

  • 그래프 내에 음의 가중치 합을 가지는 사이클이 있을 경우에, 다익스트라를 통한 최단경로를 구하는 것이 불가능합니다.

  • 그래프 내애 음의 가중치를 갖는 간선이 존재할 경우, 해당 다익스트라 알고리즘의 ‘시간복잡도 내’에 동작하지 않을 수 있습니다.

즉, 다익스트라를 사용하기 위해서는 그래프 내에 음의 가중치를 갖는 간선이 없을 경우에만 이야기하는 시간복잡도에 올바르게 동작합니다.

다익스트라는 아래와 같이 동작합니다. 그래프 내 간선의 가중치를 편의상 거리로 표현하겠습니다.

기본적으로 (시작점에서부터 다른 정점들 사이의 거리를 저장하는 배열)을 만든 이후, 시작점 자체는 거리를 0으로, 나머지 모든 정점과 시작점 사이의 거리는 무한으로 표현합니다. 또한 맨 처음에는 모든 정점들에 대해서, 최단경로로 선택되지 않았다고 기록해둡니다.

이후 다음 과정을 반복합니다.

  1. 현재 최단경로로 선택된 정점(시작점의 경우 최단경로임이 자명하기 때문에, 처음에는 시작점을 최단경로로 선택합니다)에 직접적으로 연결된, 아직 선택되지 않은 정점들을 모두 확인합니다.

  2. (선택한 정점과 확인하는 정점 사이의 거리와, 시작 정점과 선택한 정점까지의 최단거리의 합)이 현재 구해진 (시작 정점과 보고 있는 정점 사이의 거리)보다 짧을 경우, 이를 갱신해줍니다.

  3. 1, 2번 수행이 모두 끝난 이후, 아직 최단경로로 선택되지 않은 정점들 중, 시작점과의 거리가 가장 짧은 정점을 선택합니다.

  4. 3번 조건을 만족하는 정점이 존재하여 정점을 선택했다면, 현재 구한 시작점으로부터의 현재 선택한 정점 사이의 거리는 최단거리가 되므로, 해당 정점을 최단경로로 선택합니다.

  5. 최단경로로 선택하지 않은 정점이 더 이상 존재하지 않는다면, 수행을 종료합니다. 그렇지 않으면 1번으로 돌아가 수행을 반복합니다.

위와 같은 동작을 거치는 것으로 시작점에서 모든 정점으로의 최단거리가 구해짐이 보장됩니다.

증명은 다음과 같습니다.

  1. 시작점은 시작점으로부터의 최단거리임이 보장됩니다. (거리 0)

  2. 시작점으로부터 어떠한 정점으로의 최단경로가 존재한다면, 그 경로의 끝 정점의 이전단계에 있는 정점과 시작점 사이의 경로도 최단경로입니다. 만약, 그 경로가 최단경로가 아니라면, 끝 정점과 이전단계 정점을 잇는 간선의 거리와 이전단계 정점의 최단경로를 합한 경로가 현재 경로의 거리보다 더 짧음으로 시작점으로부터 끝 정점까지의 경로가 최단경로라는 가정에 모순이 생깁니다.

  3. 2번의 귀류증명에 의거하여, 현재까지 알아낸 최단경로를 찾은 정점들부터 바로 이어진 다른 정점으로의 간선을 이은 경로들 중에는 반드시 최단경로임이 보장되는 정점이 하나이상 있습니다.

  4. 3번에 의해 현재까지 최단경로를 찾은 정점들로부터 바로 이어진 다른 정점으로의 간선을 이은 경로들을 찾은 후, 아직 최단경로를 찾지 못한 정점들 중에서 시작점과의 거리가 가장 작은 정점은 최단경로입니다.

이는 다른 방법으로도 보일 수 있는데, 최단경로를 찾은 정점으로부터 경로를 만든 이후 남은 정점들 중에 거리가 가장 작은 정점이 최단경로가 아니라면, 현재까지 최단경로를 찾은 정점으로부터는 새로운 경로를 만들 수 없으므로 남은 정점들 중 거리가 가장 작은 정점 외의 정점들 중 거리가 가장 작은 정점으로의 최단경로가 존재해야 합니다. 하지만, 다른 정점에서부터는 어떠한 간선을 통해 거리가 가장 작은 정점을 이어도 현재까지 구한 거리보다 더 커지거나 같아지는 수 밖에 없으므로(다른 정점 자체의 거리가 더 크거나 같고, 간선의 거리가 음이 아니므로), 거리가 가장 작은 정점으로의 경로는 최단경로임이 보장됩니다.

그래프를 구현하는 방법은 인접행렬과 인접리스트 두 가지 방법이 있는데, 다익스트라를 구현할 때에는 인접리스트가 언제나 더 효율적이므로 인접리스트를 사용하는 것이 좋습니다. 하지만 구현 방법에 따라서, 인접행렬로 구현해도 동일한 성능을 가지도록 만들 수 있는 경우가 있어서 이 경우를 아래에 따로 이야기하겠습니다.

V^2 Dijkstra

다익스트라를 구현하는 방법은 크게 두 가지가 있습니다.

처음 소개할 방법은 다음과 같이 동작한다.

  1. 처음, 시작점을 제외한 모든 정점으로의 경로를 무한으로 합니다.

  2. 선택한 정점(처음엔 시작점)으로부터 바로 이어진 정점으로의 경로를 구하고, 그 경로의 거리가 이어진 정점으로의 거리보다 작을 경우, 경로를 갱신해줍니다.

  3. 모든 정점을 살펴보면서, 아직 방문하지 않은 정점들 중 거리가 가장 짧은 정점을 찾아서 선택해준다. 이후, 모든 정점을 선택할 때까지 2번부터 반복합니다.

그래프의 정점 수를 V, 그래프의 간선 수를 E라고 하면, 위 과정에서 이어진 정점을 선택하는데에 O(연결된 정점)이 들고, 아직 방문하지 않은 정점들 중 거리가 가장 짧은 정점을 찾는데에 O(V)이 들어 최대 O(V^2)의 시간복잡도를 갖음을 알 수 있습니다. (선택한 정점으로부터 바로 이어진 정점으로의 경로를 구하는 단계는 모든 알고리즘이 끝나면 O(E)입니다. 양 말단의 정점이 같은 간선의 경우 거리가 가장 낮은 것만 가지고 있으면 되기 때문에 이를 이용하면 언제나 E <= N^2임을 알 수 있습니다)

해당 방법을 통해 구현할 경우, 최단경로 하나를 결정하는 단계에서, 최단경로인 정점(거리가 가장 짧은 정점)을 선택하는 때에 모든 정점을 확인하여 O(V) 만큼의 시간을 사용하게 되므로, 이어진 정점을 선택하는 과정에서 O(V)까지 느려지더라도 최종 시간복잡도에 변함이 없습니다. 이를 통해, V^2 다익스트라를 구현할 때에는 인접리스트를 사용하지 않고, 인접행렬을 통해 구현해도 같은 시간복잡도를 가질 수 있습니다.

ElgE Dijkstra

다음으로 소개할 방법은 정점의 수가 많고, 간선 수는 정점의 수에 비해서는 그렇게 크지 않을 때에 사용할 수 있는 방법입니다.

앞선 방법을 통해 구현할 경우, 우리는 한 단계에서 최단경로를 선택할 때에 선형으로 정점들을 탐색해서 한 단계에 O(V)의 시간복잡도가 필요함을 알 수 있습니다. 이를 보완하기 위해, 우리가 현재까지 구한 경로들 중에 가장 거리가 짧은 경로와 정점에 대한 정보를 빠르게 알아낼 수 있다면, 해당 단계의 시간복잡도를 줄일 수 있다는 것에서 ElgE 다익스트라의 구상이 시작됩니다.

그렇다면 어떻게 하면 현재까지 구한 경로들 중 가장 짧은 경로를 더 빠르게 구할 수 있을까요? 바로 min heap을 사용하는 방법입니다.

먼저 min heap이 가지고 있는 정보는 (현재 정점, 시작점과 현재 정점 사이의 거리) 두 가지이며, 시작점과 현재 정점 사이의 거리를 기준으로 min heap을 유지합니다. 그 후 다음 단계를 반복합니다.

  1. 처음, 시작점을 제외한 모든 정점으로의 경로를 무한으로 합니다.

  2. 선택한 정점(처음엔 시작점)으로부터 바로 이어진 정점으로의 경로를 구하고, 그 경로의 거리가 이어진 정점으로의 거리보다 작을 경우, 경로를 갱신해주면서 min heap에 추가합니다.

  3. min heap의 top의 정점을 v라고 할 때에, v가 아직 선택하지 않은 정점일 때까지 heap에서 pop합니다. v가 아직 방문하지 않은 정점이라면 그 정점에서부터 2번을 반복합니다. 이 반복은 heap이 비어있지 않을 때까지 반복됩니다.

위의 경우, 최대로 heap에 들어갈 수 있는 원소의 수는 E개이며(거리의 갱신이 일어날 때에, heap에 같은 원소가 여러번 들어갈 수도 있어서 V가 아닌 E입니다) heap의 시간복잡도는 heap에 들어간 원소의 수에 비례하기 때문에 최종 시간복잡도는 O(ElgE)입니다. (이 과정에서도 경로를 갱신하는데 들어가는 시간복잡도는 O(E)입니다)

하지만 이렇게 한다고 항상 V^2 다익스트라보다 더 빠르게 동작하지는 않을 수 있습니다. 만약 그래프가 밀집(dense) 그래프이거나 혹은 완전그래프라면, E = V(V-1)/2 = 약 V^2이 되어, ElgE = V^2lgV 가 되어 오히려 V^2보다 더 느려질 수 있습니다.

이는 min heap에 값을 넣을 때에, 같은 정점에 대해 중첩된 정보가 들어갈 수 있다는 점에 있습니다.

V^2 다익스트라의 경우, 경로가 갱신될 때에, 한 정점으로의 거리가 50이었다고 해도 이후 30인 경로를 찾으면 그 경로의 값으로 덮어씌워 이전에 어떤 거리 정보들이 있었는지 확인할 필요가 없으며, 동작 중에 항상 각 정점에 대한 현재까지의 최단경로를 확인할 수 있습니다.

하지만 heap을 사용할 경우, 한 정점으로의 거리가 50, 이후에 30인 경로의 정보가 추가되어도, heap에서 50인 정보가 빠져나간 적이 없기 때문에 의미없는 정보로 더 긴 경로였던 정보들이 남아있게 됩니다. 이러한 경우가 최악의 경우 E개까지 쌓일 수 있어서 이후의 heap의 operating speed에 영향을 미치게 됩니다.

따라서, 그래프의 특수한 상황에 따라서 V^2, ElgE 다익스트라 중 어떤 것을 사용할지 선택해야 합니다.

번외

heap을 이용한 방법을 Fibonacci heap을 통해 구현하면 O(VlgV + E)로 이론적인 다익스트라의 시간복잡도를 크게 줄일 수 있습니다.

음수 사이클 & 음수 간선

먼저, 그래프 내에 음수 사이클이 있을 경우, 다익스트라가 동작되면서 무한히 음수 사이클을 돌면서 거리가 작아질 수 있습니다. 다익스트라에서는 같은 간선을 재이용하는 것을 고려하지 않기 때문에 이 상황에서 최단경로를 구할 수 없습니다.

다음으로 음수 간선을 이용할 경우, 다익스트라의 시간복잡도는 유지되지 않습니다.

이는 다익스트라의 ‘최단경로가 보장되지 않은 남아있는 정점들 중, 최소거리를 갖는 정점은 최단경로이다’가 보장되지 않으면서 발생합니다. 최단경로임이 보장되지 않는 정점에서, 음수 간선을 타고 다른 정점으로 이동한 경로가 현재 남아있는 정점들 중 최소거리보다 더 작아질 수 있기 때문입니다.

예를 들어, (1->2 : 거리 3), (1->3 : 거리 4), (3->2: 거리 -2) 인 간선들을 가진 그래프가 있다고 가정해보겠습니다.

먼저, 1번에서 연결된 간선들을 확인하면 2번으로 거리 3, 3번으로 거리 4로 이동이 가능하므로, 2번 정점이 거리 3으로 최단경로라고 확정을 짓게 될 것입니다. 하지만 이후 3번이 거리 4로 최단경로가 된 이후, (3->2: 거리 -2) 간선을 확인하면 2번 정점으로의 거리가 2가 되어 더 짧아진다는 것을 알 수 있습니다.

이러한 경우, 다익스트라를 통해 결국에는 최단경로를 찾을 수는 있으나, 이전에 ‘최단경로인 줄 알았던 경로’에서부터 살펴본 다른 경로들로 인해 시간을 소요하게 되어, 기존의 시간복잡도가 보장되지 않을 수 있습니다.

이러한 다익스트라의 성질을 이용하는 문제가 있는데, 실제 음수 간선이 존재할 수 있는 그래프 조건에서 다익스트라의 시간 복잡도가 유지되지 않는 데이터 예시를 만드는 문제입니다. 해당 문제를 풀어보면 다익스트라의 동작원리를 더 잘 이해할 수 있습니다.

APIO 2013 데이터 만들기

코드

V^2 Dijkstra

#include <bits/stdc++.h>
using namespace std;

int n, m;
int darr[1010][1010], dist[1010], visit[1010];

int main(){
	int i, j, a, s, d, S, E, min1, idx;
	scanf("%d %d", &n, &m); // n vertices, m edges
	for(i = 1; i <= n; i++){
		dist[i] = 1e9;
		for(j = 1; j <= n; j++){
			if(i != j) darr[i][j] = 1e9;
		}
	}
	for(i = 0; i < m; i++){
		scanf("%d %d %d", &a, &s, &d); // edge  (a->s : cost d)
		if(d < darr[a][s]) darr[a][s] = d;
	}
	scanf("%d %d", &S, &E); // S: start vertex, E: end vertex
	dist[S] = 0;
	for(i = 0; i < n; i++){
		min1 = 1e9; idx = 0;
		for(j = 1; j <= n; j++){
			if(!visit[j] && dist[j] <= min1) min1 = dist[j], idx = j;
		}
		if(!idx) break;
		visit[idx] = 1;
		for(j = 1; j <= n; j++){
			dist[j] = min(dist[j], dist[idx] + darr[idx][j]);
		}
	}
	printf("%d", dist[E]);
	return 0;
}

solution for 최소비용 구하기

ElgE Dijkstra

#include <bits/stdc++.h>
#define N 1010
#define M 10010
#define INF 1e9
using namespace std;

struct data{ int s, d; };
struct cmp{
	bool operator()(data d1, data d2){
		d1.d > d2.d;
	}
};
int n, m;
int darr[N], visit[N];
vector <data> vt[N];
priority_queue <data, vector<data>, cmp> pq;

int main(){
	int i, j, a, s, d, nd, flag = 0;
	scanf("%d %d", &n, &m); // n vertices, m edges
	for(i = 0; i < m; i++){
		scanf("%d %d %d", &a, &s, &d);  // edge  (a->s : cost d)
		vt[a].push_back((data){s, d});
	}
	for(i = 1; i <= n; i++) darr[i] = INF; darr[1] = 0;
	pq.push((data){1, 0});
	while(!pq.empty()){
		a = pq.top().s; pq.pop();
		if(visit[a]) continue;
		visit[a] = 1;
		for(i = 0; i < vt[a].size(); i++){
			s = vt[a][i].s; nd = vt[a][i].d;
			if(darr[s] > darr[a] + nd){
				darr[s] = darr[a] + nd;
				pq.push((data){s, darr[s]});
			}
		}
	}
	for(i = 1; i <= n; i++) printf("%d ", darr[i]);
	return 0;
}

cpp version에 따라 data를 변수, 함수, 구조체 명으로 사용할 수 없는 경우가 있으니 참고해주시길 바랍니다.