다익스트라(Dijkstra) 알고리즘
이 알고리즘은 최단 경로 문제를 해결할 수 있는 알고리즘 중 하나이다.
내가 본 바로는 네덜란드의 유명한 컴퓨터과학자 에츠허르 다익스트라가 대학생원생이던 1956년 여자 친구와 함께 컴피숍에 갔다가 20분 만에 고안해서 만든 알고리즘으로도 잘 알려져 있다고 한다.... 정말 .. 어느별에서 오신지..
다익스트라 알고리즘은 항상 노드 주변의 최단 경로만을 택하는 대표적인 그리디(Greedy) 알고리즘 중 하나로, 단순할 뿐만 아니라 실행 속도 또한 빠르다.
다익스트라 알고리즘은 임의의 정점을 출발 집합에 더할 때, 그 정점까지의 최단거리는 계산이 끝났다는 확신을 갖고 더한다. 만일 이후에 더 짧은 경로가 존재한다면 다익스트라 알고리즘의 논리적 기반이 무너진다. 이때는 모두 값을 더해서 양수로 변환하는 방법이 있으며, 이마저도 어렵다면 벨만-포드(Bellman-Ford) 알고리즘 같은, 음수 가중치를 계산할 수 있는 다른 알고리즘을 사용해야 한다. 같은 이유로 최장 거리를 구하는 데에는 다익스트라 알고리즘을 사용할 수 없다. => 파이썬 알고리즘 인터뷰 <=
위의 그림은 다익스트라 알고리즘의 진행되는 그림이다.
먼저 0번째에서 시작하여 0번에 연결되어있는 노드의 값(5, 10)을 넣는다.
여기에 넣은 5와 10은 0(시작점)에서 어느정도 떨어져 있는 지를 나타낸 값이라고 하자.
- 이 알고리즘은 가장 가까운 노드부터 방문하면서 최단거리를 확인한다.
- 5가 가장 가깝기 때문에 5를 방문하게 되고 5에 연결된 노드에 그래프에 있는 값들을 찾게 된다.
- 그러면서 5에서 10으로 가는 값이 3이라는 것을 알게되고 그럼 따라서 0에서 5까지 그리고 5에서 10으로 가는 것이 8이면 갈 수 있다는 것을 알게되고 10이라고 써져있는 노드의 값을 8로 업데이트를 하게 되는 것이다.
- 이렇게 모든 노드를 한번씩 방문을 하면서 최단거리를 업데이트 해가면서 시작점에서 어디를 가도 최단거리를 뽑게 되는 것이다.
이렇게 반복할 수 있는 코드를 작성을 해보면 아래와 같이 작성할 수 있다.
INF = int(1e9) # 아직 방문하지 않은 곳은 무한대(10억)으로 놓는다고 가정.
def dijkstra_naive(graph, start):
def get_smallest_node():
min_value = INF
idx = 0
for i in range(1, N):
if dist[i] < min_value and not visited[i]:
min_value = dist[i]
idx = i
return idx
# smallest 함수는 가장 가까운 거리부터 방문해야 하기때문에
# 가장 작은 idx 반환 함수를 만듦
#-----------------------------------------------
N = len(graph)
visited = [False] * N # 방문 체크할 변수
dist = [INF] * N # 최단 거리를 계속 업데이트할 변수
visited[start] = True # 처음 시작은 방문 처리
dist[start] = 0 # 시작점은 거리가 0이다.
for adj, d in graph[start]: # 그래프에 있는 값을 넣어준다.
dist[adj] = d
for _ in range(N - 1):
cur = get_smallest_node() # 가까운 노드를 먼저 방문
visited[cur] = True # 방문 처리
for adj, d in graph[cur]:
cost = dist[cur] + d # 나아갈 노드까지의 거리와 현재 걸어온 거리를 더해준다.
if cost < dist[adj]: # 나아갈 노드에 들어있는 값이 더 크면 업데이트 해준다.
dist[adj] = cost
return dist # 최단거리 업데이트한 dist를 반환이 코드는 이중 for문을 써서 알고리즘을 구현했기 때문에 시간 복잡도는 O(V^2) (V는 간선의 개수)이 된다. 어떻게보면 효율성이 떨어진다고 생각이 들기 때문에 이 시간을 더욱 줄일 수 있는 방법을 생각해낸다.
바로! 원소를 뺄 때, heap을 이용하여 빼는 것이다. heap은 시간 복잡도가 O(nlogn)이기 때문에 효과적으로 시간을 줄일 수 있다.
따라서 아래와 같이 구현할 수 있다.
import heapq
INF = int(1e9)
def dijkstra_pq(graph, start):
N = len(graph)
dist = [INF] * N
q = [] # 우선순위 큐
heapq.heappush(q, (0, start)) # (거리, 시작점)을 삽입
dist[start] = 0 # 시작점 거리는 0이다.
while q:
acc, cur = heapq.heappop(q)
if dist[cur] < acc: # 현재 거리변수에 있는 값보다 크면 볼 가치도 없다.
continue
for adj, d in graph[cur]:
cost = acc + d # 현재 거리와 나아갈 노드만큰 거리를 더해준다.
if cost < dist[adj]: # 나아갈 노드에 들어있는 값이 더 크면 업데이트
dist[adj] = cost
heapq.heappush(q, (cost, adj)) # 다시 넣어주며 나아간다.
return dist # 최단거리 업데이트 완료된 dist를 반환이렇게 해서 heap으로 구현한 다익스트라 알고리즘의 시간 복잡도는
O(ElogV)가 된다. (E는 노드의 개수, V는 간선의 개수)
