🚑 최단 경로를 찾아서
다익스트라❓
다익스트라(Dijkstra)알고리즘은 특정한 노드(출발점)에서 출발하여 다른 노드(도착 지점)로 가는 각각의 최단 경로를 구해주는 알고리즘이다.
특성
- 다익스트라 알고리즘은 그리디 알고리즘을 기반으로 한다.
- 음의 간선(비용이 0보다 작은 값을 가지는 간선)이 존재할 경우, 정상적인 작동 X
- 1차원 리스트에 출발 노드부터의 최소 거리를 계속해서 갱신
- 현재 처리하고 있는 노드를 기준으로 인접한 노드와의 거리 갱신
📒 원리/과정
원리
매번 가장 비용이 적은 노드를 선택
현재 처리하고 있는 노드를 기준으로 연결된 노드중 간선 비용이 가장 적은 노드를 선택하기 때문에 그리디 알고리즘에 기반한 알고리즘이라고 할 수 있다.
과정
- 출발 노드를 설정한다.
- 최단 거리 테이블을 초기화 한다.
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
- 위 과정에서 3번과 4번을 반복한다.
구현
우선순위 큐
우선순위 큐란, 기존 큐(선입 선출)와 다르게 우선순위가 높은 데이터부터 큐에서 삭제하는 자료구조이다.
파이썬에서는 우선순위 큐를 구현하기 위해 PriorityQueue 혹은 heapq 두 라이브러리를 사용할 수 있으며 알고리즘 문제는 보통 제한 시간이 있기 때문에 더 빠른 heapq를 사용해서 구현하는 것이 좋다. 우선순위 큐는 힙(heap)에 기반한 자료구조인데, heap은 최대힙과 최소힙이 있으며 각각 정점 노드가 자료의 최대값과 최소값인 완전 이진 트리로 되어있는 자료구조이다. 이 부분은 따로 더 자세히 다루도록 하겠다.
파이썬 우선순위 라이브러리들은 기본적으로 최소 힙 구조를 사용하며 이를 활용해 다익스트라 알고리즘을 구현하면 된다. 파이썬에서 heapq를 활용하여 데이터를 저장할 때 (거리, 노드 번호) 이와 같은 식으로 저장을 하면 앞에 있는 거리를 기준으로 우선순위 큐를 구성해준다.
우선순위 큐를 사용하는 이유
우선순위 큐에 대한 설명이 길어졌는데, 우선순위 큐는 오로지 다익스트라 알고리즘의 핵심인 현재 처리중인 노드에서 가장 거리가 가까운 노드로 접근하기 위해 사용하는 것이다. 기본적으로 최소 힙이기 때문에 다익스트라 알고리즘에 응용할 수가 있다.
코드
노드의 개수와 간선의 개수, 그리고 각 간선에 대한 정보(노드1, 노드2, 거리)가 차례로 주어진다고 했을 때, 우선순위 큐를 활용하여 구현한 다익스트라 알고리즘은 다음과 같다.
import heapq
N, M = map(int,input().split()) # 노드의 개수, 간선의 개수
connection = [[] for _ in range(N+1))] # 각 노드에 연결되어 있는 노드에 대한 정보를 저장할 리스트
start = int(input())
dist = [ie7]*(N+1) # 각 노드에 대한 거리를 매우 큰 값으로 초기화
for i in range(M):
A, B, cost = map(int,input().split()) # 각 노드 번호, 노드 간 거리
connection[A].append((B, cost))
q = []
heapq.heappush(q, (0, start)) # 시작 지점 거리 0으로 처리, 힙 큐에 삽입
dist[start] = 0
while q:
D, node = heapq.heappop(q) # 현재 처리중인 노드에서 가장 거리가 짧은 간선 추출
if dist[node] < D: # 입력된 현재 노드까지의 거리가 이전 노드와의 거리보다 더 짧을 경우
continue
for i in connection[node]: # 연결된 간선 확인
if D + i[1] < dist[i[0]]# 만약 현재 노드까지의 거리 + 순회중인 노드 까지의 거리가 현재 최소거리보다 작을 경우
dist[i[0]] = D + i[1]
heapq.heappush(q, (dist[i[0]], i[0]))
마치며
최단거리를 구하는 알고리즘은 대표적으로 다익스트라, 플로이드 워셜, 벨만 포드 3 가지가 있는데, 그 중 한 지점에서 다른 지점까지의 최소 거리를 구할 수 있는 다익스트라 알고리즘에 대해서 알아보았다. 이 알고리즘은 우선순위 큐를 이용해 구현할 경우 속도가 올라가며, 다른 일부 알고리즘(최소 신장 트리+프림 알고리즘)과도 유사성을 보이기 때문에 알아둔다면 더 어려운 알고리즘들의 이해에도 도움이 될 경우가 많다고 한다. 시간이 된다면 관련 문제를 풀어서 업로드 해보겠다.
