Dijkstra(다익스트라)를 내가 이해한 방식대로 설명해보기 (feat. BFS)

이번에는 Dijkstra 알고리즘에 대해서 설명을 해볼건데, 제가 이해한 방식으로 한 번 설명을 해보려고 합니다. 따라서 이게 옳은 설명인지에 대해서는 엄청 확신이 들지는 않지만 그래도 알고리즘 기본적인 작동방식을 이해하기는 쉽지 않을까 생각해봅니다. (그래서 정확한 증명보다는 이해하는데에 좀 더 집중을 하면 좋을 것 같습니다!) 그 전에 앞서서 일단 BFS 알고리즘의 특성에 대해서 설명해보도록 하겠습니다.

 

BFS

BFS(Breadth First Search)는 그래프 탐색 방법 중 하나인데, 특정 노드부터 시작해서 근처에 있는 순서대로 탐색을 하는 방법입니다. 구현을 할 때에는 주로 Queue로 구현을 하는데, Queue에 나오는 순서는 시작한 노드에 근처에 있을 수록 더 빨리 나옵니다. 이러한 특징 때문에 간선들의 비용이 모두 동일한 상황에서의 최단거리 문제에서는 BFS를 사용합니다. (예 : 미로 찾기 등의 문제에서 '출구까지의 최단거리' 등을 찾는 문제) 후술할 다익스트라 알고리즘의 시간복잡도보다 더 빠른 O(V+E)만에 풀 수 있기 때문이죠.

 

다만, BFS를 통해서 푸는 최단거리 문제는 간선들의 비용이 모두 동일한 경우에만 재미를 볼 수 있습니다. BFS를 사용해서 최단거리를 찾을 수 있는 이유는 항상 Queue에서 지금 나온 노드가 다음에 나올 노드들보다 항상 거리적으로 더 가깝거나 같기 때문인데, 만약에 간선들의 비용이 다르다면 이러한 가정이 더 이상 성립하지 않기 때문입니다. 따라서 간선들의 비용이 다르다면 그냥 BFS를 하면 안 됩니다.

 

Dijkstra

그런데 만약 가중치가 음인 간선이 없다면, 현재 찾은 노드들 및 해당 노드까지 도달한 거리에 대해서 아래와 같은 가정은 성립합니다. Queue에 {노드, 해당 노드까지 계산된 거리} 이렇게 두 가지의 정보를 넣는다면...

현재 Queue에 들어간 {노드, 해당 노드까지 계산된 거리}들 중 '해당 노드까지 계산된 거리'가 제일 짧은 거리의 노드를 우선적으로 BFS를 돌린다면, 해당 노드가 Queue에서 나온 적이 없는 경우에는 '해당 노드까지 계산된 거리' = 해당 노드까지의 최단거리가 된다.

 

만약 업데이트가 되어있다면 이미 최단 거리는 찾은 상태이니 넘어가면 됩니다. 그러면 이게 왜 성립을 하는지 설명을 해보도록 하겠습니다.

 

1. 현재 Queue에서 제일 짧은 '해당 노드까지 계산된 거리'가 k라고 합시다.

 

2. 그러면 k까지 계산된 거리를 포함해서 최단거리를 갱신하는 거리는 k 이상의 값이 될 겁니다. (음의 간선이 없기 때문이죠.)

 

3. 따라서 Queue에 이후에 들어올 '해당 노드까지 계산된 거리'는 k 이상의 값이 들어옵니다.

 

4. 이를 통해서 Queue에서 '해당 노드까지 계산된 거리'가 짧은 순서대로 BFS를 돌린다면, '해당 노드까지 계산된 거리'는 항상 단조 증가함을 보이는 걸 확인할 수 있습니다. (증가하거나, 아니면 값이 그대로거나)

 

5. 그렇다면 Queue에서 특정 노드가 아직 한 번도 Queue에서 나온적이 없으며 이번에 처음으로 나왔다면 그때 같이 '해당 노드까지의 계산된 거리'가 실제 해당 노드까지의 최단거리가 됩니다. 이후에 나오는 값들은 해당 값보다 더 크게 나오기 때문이죠.

 

그래서 Queue가 들어온 정보들 중에서 '해당 노드까지 계산된 거리'가 제일 짧은 것을 먼저 계산할 수 있도록 설계가 되어있으면 BFS를 하는 것만으로도 최단거리를 찾을 수 있습니다. 그렇다면 '해당 노드까지 계산된 거리'가 제일 짧은 것을 우선적으로 처리해줄 수 있는 자료구조가 무엇이 있을까요? 맞습니다. Priority Queue를 사용하면 됩니다. 따라서 총 시간복잡도는 Priority Queue의 시간복잡도가 O(log V)가 되므로 O((V+E) log V)가 됩니다. 이러한 알고리즘이 바로 Dijkstra입니다. (저는 이렇게 이해했습니다.)

 

그래서 Dijkstra 구현도 간단합니다. 사실상 BFS에서 Queue 대신에 Priority Queue로 바꿔주면 Dijkstra 알고리즘이 됩니다. 다만 그냥 BFS 코드에서 Priority Queue로 구현하면 실제 계산량은 제대로 구현한 것과의 차이가 엄청나기 때문에 좀 수정이 필요합니다. 잘못 구현한 Dijkstra는 저격이 가능합니다. 그래서 제대로 구현하는 방법을 꼭 알고 있어야 합니다. (그래도 BFS를 좀만 수정하기 때문에 제대로 구현하는 것도 쉬워요.)

 

Python 비스무리한 Psuedo code로 Dijkstra 구현 코드를 적으면 아래와 같습니다. PQ <- 는 Priority Queue로 push, <- PQ는 pop을 의미합니다.

 

dist[src] = 0 		# 시작점은 거리가 0으로 초기화
PQ <- {0, src} 		# PQ에 {시작점까지의 거리, 시작점}을 넣고 초기화

while PQ is not empty:
	{distance, node} <- PQ 	# distance가 제일 짧은 값과 해당되는 node를 pop
	if dist[node] < distance : continue	# node가 이미 PQ에서 나온적이 있으면 skip
	for {cost, next_node} in E[node]:
		if dist[next_node] > cost + distance:	# node를 거쳐서 가는게 더 짧다면
			dist[next_node] = cost + distance
			PQ <- {distance + cost, next_node}	
			# next_node의 최단거리를 미리 업데이트 및 PQ에 {node를 거친 next_node까지의 최단거리, next_node}를 push

 

대강 이렇게 짭니다. 중요한 점은 한 번 방문한 노드를 다시 업데이트 하지 않고, 최단거리 계산을 미리 해두어 PQ에 들어오는 정보들을 줄이도록 구현을 해야합니다.

 

여기까지 Dijkstra에 대한 설명이었습니다. 제가 증명보다는 직관적으로 이해할 수 있게 Dijkstra = BFS + Priority Queue 이렇게 야매로 설명을 한지라 제가 설명한 게 정확히 맞는 말은 아닐수도 있습니다. 그래도 작동원리에 대해서 이해하기에는 무리가 없을 것이라 생각합니다. 적어도 Dijkstra 알고리즘을 좀 더 쉽게 이해하는데에 도움이 되셨으면 좋겠습니다 :)

 

Priority Queue의 시간복잡도에 대한 추가적인 설명

그런데 왜 Priority Queue의 시간복잡도가 O(log V)가 될까요? Priority Queue에는 V개의 정보 이상이 들어올 수 있을텐데 말이죠. 맞습니다. Priority Queue에는 최대 E개의 정보들이 들어올 수 있습니다. 그런데 E는 V^2를 넘을 수가 없습니다. 그래서 O(log E) = O(log (V^2)) = O(log V)가 됩니다.