다익스트라(Dijkstra) 알고리즘

다익스트라(Dijkstra) 알고리즘은 그래프 이론을 활용한 대표적인 최단 경로(Shortest Path)탐색 알고리즘이다. 이 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 수 있는 알고리즘이다. 하지만 이 때 음의 간선을 포함하고 있는 경우 이 알고리즘은 사용할 수 없다는 점을 기억하고 이 글을 읽어보도록 하자.
 
하지만 애초에 다익스트라(Dijkstra) 알고리즘 BFS(너비 우선 탐색)을 기반으로 만들어진 알고리즘이기 때문에 BFS와 유사한 점이 많이 있다.
 
하지만 BFS는 가중치가 있는 그래프, 즉 각 간선마다 비용이 정해져 있는 경우 사용할 수 없다. 그 이유는 너비 우선 탐색은 발견한 순서부터 탐색을 시작하기 때문이다. 이 이유는 다른 장에서 따로 설명하도록 하겠다.
 

다익스트라 알고리즘과 BFS의 차이

다익스트라 알고리즘과 BFS의 궁극적인 차이는 역시 위에서 말한대로 탐색 순서에 차이가 있다고 할 수 있다.
 
다음 두 가지가 다익스트라 알고리즘과 BFS에서 사용되는 자료구조이다.

• 다익스트라 - 우선순위 큐
• BFS - 큐

이 차이가 탐색에 차이를 두게 한다.

다익스트라 알고리즘의 구조

다익스트라 알고리즘의 구조는 BFS에서 파생되었기 때문에 구조는 비슷하다. 하지만 이 알고리즘은 특정 정점에서 각 정점까지의 최소 거리만을 구하는 알고리즘이기 때문에 각 정점까지의 최단 거리를 저장하는 배열 dist[]를 유지하며, 정점을 방문할 때마다 인접한 정점을 모두 검사한다.
 
예를 들어, 간선 (u, v)를 검사했는데 v가 만약 아직 방문하지 않은 정점이라고 가정해보자. 그러면 u까지의 최단 거리에 간선 (u, v)의 가중치를 더해 v까지의 경로의 길이를 찾는 것이다. 이것이 지금까지 우리가 찾은 최단 거리라면 dist[v]를 갱신하고 (v, dist[v])를 우선순위 큐에 넣는 구조이다.
 
이때, 유의해야할 점이 있다.

•  각 정점까지의 거리가 갱신될 수 있다.

자 그럼 아래 그림을 보도록 하자.

그림 1.1

 
그림 1.1을 보고 설명을 하도록 하겠다. A에서 시작을 한다고 가정하자. 시작점 A를 방문하게 되었을 경우 (2, B)와 (12, C)가 우선순위 큐에 들어가게 된다. 최단 거리 순으로 정점들을 큐에서 꺼내는 다익스트라 알고리즘의 구조상 (12, C)는 그대로 큐에 있고 정점 B와 D를 순차적으로 방문할 것이다.
 
문제는 D에 방문했을 때이다. D까지의 최단 경로에 (D, C) 간선의 가중치를 더한다면 시작점 A에서 C까지로 가는 비용이 9인 경로를 찾을 수 있게 된다. 이것은 위에서 먼저 (12, C)의 경로보다 짧은 것이다. 이때 dist[C]를 갱신한다고 하더라도 이미 우선순위 큐에 들어있는 (12, C)는 어떻게 처리하느냐가 문제다.
 
이때 사용할 수 있는 방법이 두 가지이다.

1. 우선순위 큐 내에서 (12, C)를 찾아내 (9, C)로 바꾼다.
2. (12, C)를 그대로 두고 (9, C)를 추가한 뒤, 나중에 큐에서 (12, C)가 꺼내지면 무시한다.

보통은 우리가 사용하는 방법이 바로 2번이다.
 
이 방법을 사용한다면 (12, C)가 무시되어야 하기 때문에 최단 경로가 갱신되어 있는 dist[C]와 현재 큐에서 불려진 요소 (12, C)의 비용을 비교하면 된다. 만약 dist[u] < cost, 즉 dist[C] < 12라면, u까지 오는 cost보다 짧은 경로가 이미 발견됐다는 의미이므로 (12, C) 쌍은 무시하면 된다.

간선의 가중치가 음수일 때 안되는 이유

위의 구조로 인하여 다익스트라 알고리즘이 해당 노드를 방문했다는 것은 두번 다시 해당 정점을 방문할 이유가 없다는 것이다.
 
다음과 같은 그래프를 보도록 하자.

다익스트라 알고리즘의 구조상 (3, 1)과 (4, 2) 순서대로 우선순위 큐에 넣어질 것이다. 이렇게 된다면 1번 노드를 먼저 방문하게 되고 이는 곧 1번 노드로 가는 최단 경로의 비용이 3이라는 것을 의미한다.
 
하지만 우리는 0→2→1 순으로 방문하여 최단 거리 비용이 4 - 2 = 2인것을 알 수 있다.
 
이렇듯 다익스트라 알고리즘은 구조적으로 한 번 방문했던 노드는 두 번 다시 보지 않기 때문에 간선의 가중치가 음수일 경우에는 작동하지 않는 것을 알 수 있다.
 
이럴때 사용할 수 있는 대표적인 알고리즘으로는 벨만 포드 알고리즘이 있다.

정당성의 증명

다익스트라 알고리즘은 너비 우선 탐색에서 파생된거기 때문에 최단 거리를 잘 구할 것이라고 예상은 할 수 있지만, 정확한 증명을 위해서 귀류법을 사용할 필요가 있다.
 
이를 위해 다익스트라 알고리즘이 최단 거리를 계산하지 못하는 정점 U가 있다고 가정해보자.
 
우선 이 알고리즘은 시작점에 대해서는 항상 정확하게 최단 거리를 계산하기 때문에 정점 U는 시작점이 아니라는 것을 알 수 있다. 왜냐하면 시작점은 0이 되기 때문이다.
 
그러면 U를 방문한 순간 두 가지 그래프를 그릴 수 있다.

1. U 이전에 방문한 정점들
2. 아직 방문하지 않은 정점들

이때 U에 대한 최단 거리를 잘못 계산했다는 것은 다익스트라 알고리즘이 만든 스패닝 트리에서의 경로보다 더 짧은 경로가 존재한다는 것이다. 다음 그림을 보도록 하자.

그림 1.2

 
그림 1.2를 보도록 하자. 다익스트라 알고리즘으로는 초록색 간선으로 끝나는데, 이보다 빨간선으로 표시된 경로가 더 짧다고 가정해보자.
 
우선 상황은 U가 Q보다 먼저 방문되었다는 상황이다. 하지만 초록색 간선으로 가는 것 보다 빨간색 간선으로 가는게 더 비용이 적게 든다면 빨간색 간선을 타고 따라가다 보면 언젠가 이미 방문한 정점을 만나게 될 것이다.
 
그러면 이미 방문한 정점 P, 그 직전에 만나는 정점을 Q라고 했을 때 시작점부터 Q까지의 최단 거리는 dist[P] + w(P, Q)가 된다. 그런데 P는 이미 방문한 상태이기 때문에, dist[Q]에는 이 최단 거리가 이미 저장되어 있고 Q는 우선순위 큐에 들어가 있다는 것을 의미한다.
 
두 정점 U와 Q중에서 U가 먼저 꺼내졌다는 것은 dist[U]<=dist[Q]임을 알려준다.
 
즉, 이는 Q를 지나서 U로 오는 경로가 dist[U]보다 짧다는 가정은 모순이 된다는 것이다.
 
이와 같이 스패닝 트리 위의 경로보다 짧은 경로는 존재할 수 없으므로, 다익스트라 알고리즘이 찾아내는 경로가 항상 최단 경로라는 결론을 우리는 알 수 있다.

구현

// 정점의 개수
int V;
// 그래프의 인접 리스트, (간선 가중치, 정점) 쌍을 담는다.
vector<pair<int, int> > adj[MAX_V];
vector<int> Dijkstra(int src)
{
	vector<int> dist(V, INF);
	dist[src] = 0;
	priority_queue<pair<int, int> > pq;
	pq.push(make_pair(0, src));
	while (!pq.empty())
	{
		int here = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();
		// 만약 지금 꺼낸 것보다 더 짧은 경로를 알고 있다면 꺼금 꺼낸 것을 무시한다.
		if (cost > dist[here])
			continue;
		// 인접한 정점들을 모두 검사한다.
		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adf[here][i].first;
			int nextDist = cost + adj[here][i].second;
			// 더 짧은 경로를 발견하면, dist[]를 갱신하고 우선순위 큐에 넣는다.
			if (dist[there] > nextDist)
			{
				dist[there] = nextDist;
				pq.push(make_pair(-nextDist, there));
			}
		}
	}
	return dist;
}

시간 복잡도

각 정점은 정확히 한 번씩 방문된다는 점을 생각하면 간선들을 검사하는 데는 전체 O(|E|)의 시간이 걸림을 알 수 있다.
 
우선순위 큐에 원소를 넣고 삭제하는 데 드는 총 시간을 분석하기 위해서는 우선순의 큐의 최대 크기가 얼만지 알아야 한다. 만약 그냥 BFS라면 큐에 모든 정점이 한번씩 들어가기 때문에 O(|V|)가 되지만 다익스트라 알고리즘은 거리가 갱신될 때마다 우선순위 큐에 정점이 들어가게 된다. 그렇기 때문에 더 많은 원소가 들어갈 수 있게 된다.
 
우선순위가 가장 커지는 최악의 시나리오는 그래프의 모든 간선이 검사될 때마다 dist[]가 갱신되는 것이다. 즉, 각 간선을 검사할 때마다 일어나는 것이기 우선순위 큐에 추가되는 원소의 수는 최대 O(|E|)가 된다. 이 경우 우선순위 큐에 추가하거나 삭제하는 데는 O(lg|E|)의 시간이 걸리고, 이를 O(|E|)개의 원소에 대해 이 작업을 하게 되면 전체 시간 복잡도는 O(|E|lg|E|)가 된다.
 
그러면 간선들을 검사하는데 O(|E|) 그리고 우선순위 큐의 최대 크기와 최대 크기의 간선을 검사하는데 O(|E|lg|E|)가 된다. 즉, O(|E| + |E|lg|E|)=O(|E|lg|E|)가 시간 복잡도가 된다는 것을 알 수 있다.
 
대개의 경우 그래프에서 간선의 개수 |E|는 |V|^2보다 작기 때문에 O(lg|E|)=O(lg|V|)가 된다. 따라서 시간 복잡도는 O(|E|lg|V|)가 된다.

출처

종만북

이론

https://deulee.tistory.com/11

BFS는 왜 가중치가 있는 그래프에서 사용할 수 없을까?