데이터 과학 유망주의 매일 글쓰기 — 쉬어가는 시간 4–3
다익스트라의 알고리즘(Dijkstra’s Algorithm)
# Dijkstra, # Algorithm
오늘 한일:
어제는 평행, 동시성 및 분산에 대해 알아보았다. 컴퓨터 공학에서 많은 프로세스를 효율적으로 수행할 수 있도록 해주는 개념들로써, 앞으로 좋은 개발자가 되기위해 필요한 도구들이라는 생각이 들었다.
이번 섹션에서 몇 번 언급되고, 또 궁금했던 다른 주제 중 하나는 다익스트라 알고리즘(Dijkstra’s Algorithm)이라는 것이었다. 그래프 상에서 출발지부터 목적지까지 가장 빠른 길을 찾는 방법 중 하나로써, 너비우선검색(Breadths First Search, BFS)의 대안으로 볼 수 있다. 그렇다면, 이 알고리즘은 도대체 무엇일까?
다익스트라 알고리즘(Dijkstra’s Algorithm)
이전에 소개한 것처럼 “그래프 상에서 시작 노드부터 목적 노드까지 가장 빠른 길을 찾아내는 것"이 목적인 알고리즘이다. 가장 빠른 길이 그래프 상의 모든 노드를 포함하지 않을 수 있다는 점에서 Minimum Spanning Tree와는 다른 형태의 알고리즘이라 할 수 있다.
작동 방법
다익스트라 알고리즘은 간단하게 말해서 아래와 같은 개념이다.
노드 “A”와 “D”사이에 존재하는 가장 빠른 지름길인 “A -> D”에 포함되는 “B -> D”라는 길이 있다면, 이는 노드 “B”와 “D”사이에 존재하는 가장 빠른 지름길이기도 하다.
즉, 출발 노드와 목적 노드 사이에 존재하는 지름길에 다른 노드부터 목적 노드까지의 길이 있다면, 그 지름길은 해당 노드부터 목적 노드 까지의 지름길이기도 하다는 것이다.
이 개념을 고안한 에드거 다익스트라(Edsger Dijkstra)는 시작 노드와 목적 노드 사이를 반대 방향으로 연산했다. 즉, 시작 노드로부터 각 노드까지의 거리를 “과다측정”한 것이다. 이후 각 노드와 이웃노드를 방문하면서, 각 노드와 이웃노드 사이의 지름길을 찾는 방법을 택했다.
이 알고리즘은모든 상황에서 가장 빠른 길을 찾으려 하고, 그것이 전체 문제에 대한 가장 최적의 답이라는 것을 전제로 하기 때문에, Greedy 방법론이라 볼 수 있다.
다익스트라 알고리즘의 예
조금 더 쉽게 예제를 들어 알아보자. 일단 아래와 같은 Weighted Graph를 가정한다.
- 아래와 같이 시작 노드를 선택하고, 다른 모든 노드의 값을 무한(Infinite)으로 설정한다.
2. 각 노드를 방문하면서, 각 Edge의 길이를 업데이트한다.
3. 각 인접 노드와의 길이가 새로 업데이트된 길이보다 작다면, 업데이트하지 않는다.
4. 이미 방문한 노드와의 거리는 업데이트하지 않는다.
5. 모든 반복이 끝나면, 방문하지 않은 노드 중 가장 짧은 거리를 선택한다. 그러므로 7이 아닌 5를 선택하여 가장 짧게 계산된 거리를 업데이트한다.
6. 가장 오른쪽에 있는 노드는 길이가 2번 업데이트된다. 즉, 7을 한번 더 선택해 더 짧은 거리를 형성할 수 있는지 체크한다. 만약 더 크다면 원래 갚을 그대로 유지한다.
7. 위 1–6번 과정을 반복하여, 모든 노드사이의 거리가 업데이트 될때까지 연산한다.
의사코드(Pseudocode)
모든 노드 사이의 거리를 유지하는 것이 목표다. 거리 정보를 저장할 수 있는 노드 수 만큼의 배열을 생성할 수 있다.
또한, 가장 짧은 거리를 찾는 것 뿐만이 아니라, 가장 짧을 거리의 전체 길이를 알아야한다. 이를 위해서는, 각 노드를 가장 마지막에 업데이트한 다른 노드에 맵핑할 수 있다.
알고리즘 연산이 끝나면, 목적 노드로부터 시작 노드까지 역추적(Backtracking)하는 방식으로 길을 찾게 된다.
가장 짧은 거리를 가진 노드를 효율적으로 저장하기 위해 최소 우선순위 Queue를 사용할 수 있다.
# 다익스트라 알고리즘 의사코드
def dijkstra(G, S) # "G"는 그래프, "S"는 시작 노드
for each node "V" in "G"
distance[V] <- infinite # 초기 거리 무한대 설정
previous[V] <- NULL # 이전 값은 NULL
If V != S, add V to Priority Queue Q # V가 S와 같지 않다면, V를 Queue에 저장
distance[S] <- 0 # 목적지 초기화
while Queue IS NOT EMPTY # Queue에 아무것도 없을 때까지 반복
U <- Extract MIN from Queue # Queue의 최소값 "U"를 설정
for each unvisited neighbour V of U # 특정 노드 U의 방문하지않은 각 이웃노드 V를 모두 방문
tempDistance <- distance[U] + edge_weight(U, V) # 노드 U와 연결된 모든 이웃노드 "V"까지의 거리를 총합
if tempDistance < distance[V]
distance[V] <- tempDistance
previous[V] <- U
return distance[], previous[] 코드로 구현한 다익스트라 알고리즘
위 의사코드에 기반해 아래와 같이 코드를 작성할 수 있다.
# 다익스트라의 시작점부터 도착점까지 찾는 단일 지름길 알고리즘 [참조: (11)]
# 그래프의 인접 매트릭스(Adjacent Matrix)활용 # INT_MAX에 필요한 라이브러리 import sys
# 그래프 클래스 생성class Graph():
# 생성자 함수, list comprehension으로 모든 노드의 수만큼 그래프 사이즈 생성 def __init__(self, vertices): self.V = vertices self.graph = [[0 for column in range(vertices)]
# 솔수션을 출력하는 함수 (거리값이 인자) def printSolution(self, dist): print "Vertex \tDistance from Source" # 보는 사람의 편의를 위해 시작점 기준 각 노드와의 거리 안내 출력 for node in range(self.V): # 모든 노드의 수만큼 연산 반복 print node, "\t", dist[node] # 노드와 거리를 출력 # 각 노드사이에 존재하는 가장 짧은 거리를 가진 노드 찾기 함수 def minDistance(self, dist, sptSet): # 다음 노드와의 최소거리 초기화 min = sys.maxint # 가장 가까이 있는 노드가 아닌 노드 검색, 가장 짧은 거리에 없는 것 for v in range(self.V): if dist[v] < min and sptSet[v] == False: # 만약 거리가 최소값보다 짧다면 최소거리를 해당 거리값으로 다시 업데이트 min = dist[v] min_index = v return min_index # 최소값을 가진 노드 인덱스 업데이트 # 인접 매트리스로 표현된 그래프에서, 한 시작점에서 가장 빠른 길을 찾을 수 있는 알고리즘을 구현한 함수 def dijkstra(self, src):
# 가장 높은 값과 노드의 값을 곱해 업데이트 dist = [sys.maxint] * self.V dist[src] = 0 # 시작점과의 거리 초기화 sptSet = [False] * self.V for cout in range(self.V): # 노드 V만큼 연산 반복 # 모든 노드에서 아직 방문하지 않은 최소거리를 갖는 노드를 선택. 첫 연산에서 "u"는 항상 시작점으로 간주 u = self.minDistance(dist, sptSet) # 가장 짧은 거리를 저장하는 곳에 최소거리를 갖는 노드를 저장 sptSet[u] = True
# 지정된 노드의 현재 거리가 업데이트된 거리보다 짧고, 가장 짧은 거리에 저장되지 않은 노드가 있는 경우 지정된 노드에서 인접 노드까지의 거리를 업데이트 하는 함수 for v in range(self.V): if self.graph[u][v] > 0 and sptSet[v] == False and \ dist[v] > dist[u] + self.graph[u][v]: dist[v] = dist[u] + self.graph[u][v] self.printSolution(dist) #최종 거리정보 출력# 테스트 코드g = Graph(9) # 9개의 노드를 가진 그래프 구현g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0], # 각 노드의 초기값 생성 (인접 매트리스 활용[4, 0, 8, 0, 0, 0, 0, 11, 0],[0, 8, 0, 7, 0, 4, 0, 0, 2],[0, 0, 7, 0, 9, 14, 0, 0, 0],[0, 0, 0, 9, 0, 10, 0, 0, 0],[0, 0, 4, 14, 10, 0, 2, 0, 0],[0, 0, 0, 0, 0, 2, 0, 1, 6],[8, 11, 0, 0, 0, 0, 1, 0, 7],[0, 0, 2, 0, 0, 0, 6, 7, 0]];g.dijkstra(0); # 노드 0부터 시작# This code is contributed by Divyanshu Mehta
시간복잡도와 공간복잡도
노드의 수가 로그 단위로 증가하고 그것이 Edge의 수만큼 증가하기 때문에 시간복잡도는 로그시간인 O(ElogV)에 수렴한다.
공간복잡도는 노드 개수만큼 데이터가 저장되어야하므로, 선형시간인 O(V)에 수렴한다.
다익스트라 알고리즘의 실생활활용
다익스트라 알고리즘은 특정한 지점이나 사물을 기준으로 가장가까운 다른 대상을 찾는 모든 어플리케이션에 활용될 수 있다.
- 시작점과 목적지 사이에 가장 빠른 길 찾기(자동차 내비게이션 등)
- 소셜 내트워크 분석(나와 가장 가까운 사람들 찾기 등)
- 무선 전화 및 통신 네트워크 구성
- 지도 상에서 위치를 찾는 GPS 어플리케이션
앞으로 할일:
오늘은 다익스트라 알고리즘에 대해 알아보았다. 이 알고리즘이 Greedy한 방법인지 몰랐다. 어쨌든 가장 빠른 솔루션을 찾기 위해서는 Greedy알고리즘 만한게 없으니 이 알고리즘이 그만큼 많이 언급된 것 같기도하다.
BFS나 이 다익스트라 알고리즘이나, 내게는 구현하기 쉽지 않은 이론들이다. 아직도 어떻게 해야 코드로 구현할 수 있는지에 대한 감이 안 잡힌다. 조금 더 리뷰하고 더 제대로 이해하기 위해 노력해보아야할 것 같다.
배우면 배울 수록 헷갈리는 것이 많다. 특히 머리로는 이해했는데, 컴퓨터 코드로는 어떻게 구현해야할지 감이 안 잡히는 막막한 개념들이 있다. 하지만, 이런 개념들을 잘 터득해야 좋은 개발자나 데이터 과학자가 될 수 있는 것도 사실이다.
나는 개인적으로 이번 컴퓨터 과학의 기초를 다지는 시간이 가장 어려웠다. 특히, 알고리즘을 코드로 구현하는 부분이 그 어느 때보다 어려웠다. 웹 프로그래밍을 할 때는 이정도로 복잡하다고 느끼지는 못했다. 알고리즘을 잘해야 정말 프로그래밍을 잘 한다는 소리를 들을 수 있는 만큼, 이 개념을 잘 숙지하고, 기본적인 것들은 자유자재로 코드로 구현할 수 있도록 연습해야겠다.
인간은 나이가 들면서, 많이 퇴회되는 면이 있다고 한다. 나는 그 점이 조금 두렵기도하다. 내가 어느덧 30줄에 들면서, 예전처럼 많은 것들을 빨리 학습하기가 쉽지 않은 것 같다고 느껴지기도 한다. 아직까지는, 큰 어려움은 없다. 하지만, 내가 꾸준히 머리를 쓰려 노력하는한, 그리 쉽게 퇴화하지는 않을 것이라 믿는다.
이 세상에 쉬운 것은 없다. 그러나 노력해서 안될 수 있는 것도 그리 많지 않다. 그렇기에 노력할 것이다. 배울 수 있는 지금이, 내 두뇌가 활발한 지금이 새로운 것을 소화시킬 가장 적기다. 내 두뇌가 더 이상 돌아가지 않을 그 때가 언제인지 모르지만, 그 때가 오기전까지 최대한 두뇌를 운동시킨다면, 그만큼 지적인 생명체로 더 오래 살아갈 수 있지 않을까? 물론 과로시키면 안될 것이다. 그 것을 위해 건강관리도 잘 해야할 것이다.
모든 사람이 건강하게 오랫동안 많은 것을 배울 수 있기를.
참조:
(1) https://www.youtube.com/watch?v=Lfb8qkXzHY0
(2)~(10) https://www.programiz.com/dsa/dijkstra-algorithm
(11) https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-greedy-algo-7/
