다익스트라 알고리즘
26 Nov 2017 | Dijkstra's algorithm Shortest path Graph
이번 글에서는 최단 경로(Shortest Path)를 찾는 대표적인 기법 가운데 하나인 다익스트라 알고리즘(Dijkstra’s algorithm)을 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님과 역시 같은 대학의 김황남 교수님 강의와 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
concept
다익스트라 알고리즘은 너비우선탐색(BFS)을 기본으로 합니다. 하단 좌측과 같은 그래프를 대상으로 다익스트라 알고리즘을 적용해 보겠습니다. 우선 시작노드를 제외한 모든 노드의 거리정보를 무한대로 초기화합니다. 시작노드 $s$를 탐색하고 있다(processing)는 의미로 gray를 칠해둡니다.
(b)를 보겠습니다. 시작노드 $s$를 기준으로 BFS를 적용합니다. $s$에 바로 이웃한 $t$와 $y$에 대해 거리정보를 업데이트한 뒤 $s$ 방문을 마쳤다는 의미로 black을 칠해둡니다. 다음 BFS 적용 대상은 방문하지 않은(white) 노드들 가운데 거리가 최소인 노드입니다. $y$가 5로 가장 작군요. $y$를 탐색하고 있다는 의미로 gray를 칠해둡니다.
(c)를 보겠습니다. $y$에 바로 이웃한 $t,x,z$에 대해 거리정보를 업데이트합니다. 시작노드 $s$와 $t$ 사이의 기존 최단거리는 10이었습니다. 그런데 ($s$와 $y$ 사이의 최단거리)+($y$와 $t$ 사이의 거리)=5+3=8이므로, $s$와 $t$ 사이의 최단거리를 8로 바꾸고, 최단경로를 $y$를 경유하게끔 업데이트합니다(edge relaxation). 나머지 $x,z$도 이렇게 수행합니다. 이후 $y$ 방문을 마쳤다는 의미로 black을 칠해 둡니다. 다음 BFS 적용 대상은 거리가 7로 가장 작은 미방문 노드인 $z$입니다. 탐색하고 있다는 의미로 gray를 칠해 둡니다.
(d)를 보겠습니다. $z$를 기준으로 BFS를 적용합니다. $z$에 바로 이웃한 $y,x$에 대해 거리정보를 업데이트합니다. $y$는 이미 방문을 마쳤으므로(black) 건너뛰고 $x$만 처리합니다. $s$와 $x$ 사이의 기존 최단거리는 14였습니다. 그런데 ($s$와 $z$ 사이의 최단거리)+($z$와 $x$ 사이의 거리)=7+6=13으로 기존보다 작으므로, $s$와 $x$ 사이의 최단거리를 13으로 바꾸고, 최단경로를 $z$를 경유하게끔 업데이트합니다. 이후 $z$ 방문을 마쳤다는 의미로 black을 칠해 둡니다. 다음 BFS 적용 대상은 거리가 8로 가장 작은 미방문 노드인 $t$입니다. 탐색하고 있다는 의미로 gray를 칠해 둡니다.
(e)를 보겠습니다. $t$를 기준으로 BFS를 적용합니다. $t$에 바로 이웃한 $x$에 대해 거리정보를 업데이트합니다. $s$와 $x$ 사이의 기존 최단거리는 13였습니다. 그런데 ($s$와 $t$ 사이의 최단거리)+($t$와 $x$ 사이의 거리)=8+1=9로 기존보다 작으므로, $s$와 $x$ 사이의 최단거리를 9로 바꾸고, 최단경로를 $t$를 경유하게끔 업데이트합니다. 이후 $t$ 방문을 마쳤다는 의미로 black을 칠해 둡니다. 다음 BFS 적용 대상은 거리가 9로 가장 작은 미방문 노드인 $x$입니다. 탐색하고 있다는 의미로 gray를 칠해 둡니다.
마지막으로 (f)를 보겠습니다. $x$를 기준으로 BFS를 적용합니다. $x$에 바로 이웃한 $z$에 대해 거리정보를 업데이트합니다. 그런데 $z$는 이미 방문을 마쳤으므로 건너뜁니다. 더 이상 처리할 이웃노드가 없으므로 $x$ 탐색을 마치고 black을 칠해 둡니다.
이로써 모든 노드 방문을 마쳤습니다. 다익스트라 알고리즘을 종료합니다. 다익스트라 알고리즘의 의사코드는 다음과 같습니다.
계산복잡성
하나의 노드에 대해 다익스트라 알고리즘을 수행하는 경우를 따져보겠습니다. 미방문노드 가운데 거리가 가장 작은 노드에 BFS를 적용합니다. 거리를 가장 작은 미방문노드를 가려내려면 최악의 경우 노드 전체를 모두 따져봐야 하므로 $O($|$V$|$)$입니다. 선택된 노드의 모든 이웃노드들에 대해 최단경로 정보를 업데이트합니다. 한 노드당 엣지의 기대값은 |$E$|/|$V$|입니다.
다익스트라 알고리즘은 이러한 연산을 전체 노드 수만큼 반복하므로 전체적인 계산복잡성은 $O($|$V$|$^2+$|$E$|$)$가 됩니다. 보통의 dense graph는 엣지의 수가 노드 수의 제곱만큼 있으므로 간략하게 계산복잡성을 적으면 $O($|$V$|$^2)$이 됩니다.
단점
다익스트라 알고리즘의 최대 단점은 가중치가 음수인 경우 작동하지 않는다는 점입니다. 이를 도식화한 그림은 다음과 같습니다.
만일 음수인 가중치를 갖는 엣지가 포함된 그래프에 대해 다익스트라 알고리즘을 적용하려고 할 경우, 그래프 전체에서 가장 작은 가중치의 절대값만큼을 모든 엣지 가중치에 더해준 뒤 다익스트라 알고리즘을 적용하고, 적용이 끝난 이후 해당 절대값만큼을 다시 빼서 결과를 내는 방식으로 수행할 수도 있습니다.
이번 글에서는 최단 경로(Shortest Path)를 찾는 대표적인 기법 가운데 하나인 다익스트라 알고리즘(Dijkstra’s algorithm)을 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님과 역시 같은 대학의 김황남 교수님 강의와 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.
concept
다익스트라 알고리즘은 너비우선탐색(BFS)을 기본으로 합니다. 하단 좌측과 같은 그래프를 대상으로 다익스트라 알고리즘을 적용해 보겠습니다. 우선 시작노드를 제외한 모든 노드의 거리정보를 무한대로 초기화합니다. 시작노드 $s$를 탐색하고 있다(processing)는 의미로 gray를 칠해둡니다.
(b)를 보겠습니다. 시작노드 $s$를 기준으로 BFS를 적용합니다. $s$에 바로 이웃한 $t$와 $y$에 대해 거리정보를 업데이트한 뒤 $s$ 방문을 마쳤다는 의미로 black을 칠해둡니다. 다음 BFS 적용 대상은 방문하지 않은(white) 노드들 가운데 거리가 최소인 노드입니다. $y$가 5로 가장 작군요. $y$를 탐색하고 있다는 의미로 gray를 칠해둡니다.
(c)를 보겠습니다. $y$에 바로 이웃한 $t,x,z$에 대해 거리정보를 업데이트합니다. 시작노드 $s$와 $t$ 사이의 기존 최단거리는 10이었습니다. 그런데 ($s$와 $y$ 사이의 최단거리)+($y$와 $t$ 사이의 거리)=5+3=8이므로, $s$와 $t$ 사이의 최단거리를 8로 바꾸고, 최단경로를 $y$를 경유하게끔 업데이트합니다(edge relaxation). 나머지 $x,z$도 이렇게 수행합니다. 이후 $y$ 방문을 마쳤다는 의미로 black을 칠해 둡니다. 다음 BFS 적용 대상은 거리가 7로 가장 작은 미방문 노드인 $z$입니다. 탐색하고 있다는 의미로 gray를 칠해 둡니다.
(d)를 보겠습니다. $z$를 기준으로 BFS를 적용합니다. $z$에 바로 이웃한 $y,x$에 대해 거리정보를 업데이트합니다. $y$는 이미 방문을 마쳤으므로(black) 건너뛰고 $x$만 처리합니다. $s$와 $x$ 사이의 기존 최단거리는 14였습니다. 그런데 ($s$와 $z$ 사이의 최단거리)+($z$와 $x$ 사이의 거리)=7+6=13으로 기존보다 작으므로, $s$와 $x$ 사이의 최단거리를 13으로 바꾸고, 최단경로를 $z$를 경유하게끔 업데이트합니다. 이후 $z$ 방문을 마쳤다는 의미로 black을 칠해 둡니다. 다음 BFS 적용 대상은 거리가 8로 가장 작은 미방문 노드인 $t$입니다. 탐색하고 있다는 의미로 gray를 칠해 둡니다.
(e)를 보겠습니다. $t$를 기준으로 BFS를 적용합니다. $t$에 바로 이웃한 $x$에 대해 거리정보를 업데이트합니다. $s$와 $x$ 사이의 기존 최단거리는 13였습니다. 그런데 ($s$와 $t$ 사이의 최단거리)+($t$와 $x$ 사이의 거리)=8+1=9로 기존보다 작으므로, $s$와 $x$ 사이의 최단거리를 9로 바꾸고, 최단경로를 $t$를 경유하게끔 업데이트합니다. 이후 $t$ 방문을 마쳤다는 의미로 black을 칠해 둡니다. 다음 BFS 적용 대상은 거리가 9로 가장 작은 미방문 노드인 $x$입니다. 탐색하고 있다는 의미로 gray를 칠해 둡니다.
마지막으로 (f)를 보겠습니다. $x$를 기준으로 BFS를 적용합니다. $x$에 바로 이웃한 $z$에 대해 거리정보를 업데이트합니다. 그런데 $z$는 이미 방문을 마쳤으므로 건너뜁니다. 더 이상 처리할 이웃노드가 없으므로 $x$ 탐색을 마치고 black을 칠해 둡니다.
이로써 모든 노드 방문을 마쳤습니다. 다익스트라 알고리즘을 종료합니다. 다익스트라 알고리즘의 의사코드는 다음과 같습니다.
계산복잡성
하나의 노드에 대해 다익스트라 알고리즘을 수행하는 경우를 따져보겠습니다. 미방문노드 가운데 거리가 가장 작은 노드에 BFS를 적용합니다. 거리를 가장 작은 미방문노드를 가려내려면 최악의 경우 노드 전체를 모두 따져봐야 하므로 $O($|$V$|$)$입니다. 선택된 노드의 모든 이웃노드들에 대해 최단경로 정보를 업데이트합니다. 한 노드당 엣지의 기대값은 |$E$|/|$V$|입니다.
다익스트라 알고리즘은 이러한 연산을 전체 노드 수만큼 반복하므로 전체적인 계산복잡성은 $O($|$V$|$^2+$|$E$|$)$가 됩니다. 보통의 dense graph는 엣지의 수가 노드 수의 제곱만큼 있으므로 간략하게 계산복잡성을 적으면 $O($|$V$|$^2)$이 됩니다.
단점
다익스트라 알고리즘의 최대 단점은 가중치가 음수인 경우 작동하지 않는다는 점입니다. 이를 도식화한 그림은 다음과 같습니다.
만일 음수인 가중치를 갖는 엣지가 포함된 그래프에 대해 다익스트라 알고리즘을 적용하려고 할 경우, 그래프 전체에서 가장 작은 가중치의 절대값만큼을 모든 엣지 가중치에 더해준 뒤 다익스트라 알고리즘을 적용하고, 적용이 끝난 이후 해당 절대값만큼을 다시 빼서 결과를 내는 방식으로 수행할 수도 있습니다.
Comments