Hey Tech
다익스트라 최단 경로 알고리즘 이해 (+Python 구현) 본문
📚 목차
1. 최단경로(길찾기) 알고리즘이란?
2. 다익스트라 최단경로 알고리즘이란?
3. 다익스트라 최단경로 알고리즘의 동작 과정
4. 구현 방법1: 일반적인 구현
4.1. 코드 해설
4.2. 전체 코드
4.3. 시간 복잡도
5. 구현 방법2: 시간 복잡도 개선
5.1. 우선순위 큐(Priority Queue) 자료구조
5.2. 힙(Heap) 자료구조
5.3. 우선순위 큐 자료구조 기반의 알고리즘 동작 과정
5.4. 우선순위 큐 자료구조 기반 알고리즘 구현(Python)
1. 최단경로(길찾기) 알고리즘이란?
최단경로 알고리즘은 길찾기 알고리즘이라고도 불리며, 말 그대로 특정 지점까지 가장 빠르게 도달할 수 있는 경로를 찾는 알고리즘입니다. 알고리즘 테스트에서 빈출 최단경로 알고리즘 유형은 아래와 같습니다.
- 다익스트라 최단경로 알고리즘(Dijkstra Algorithm)
- 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)
이번 포스팅에서는 다익스트라 최단경로 알고리즘에 대해 알아봅니다. 플로이드 워셜 알고리즘은 이곳을 참고해 주세요!
2. 다익스트라 최단경로 알고리즘이란?
다익스트라 최단경로 알고리즘은 특정 노드에서 출발하여 다른 특정 노드로 가는 최단경로를 계산할 때 사용하는 알고리즘입니다. 노드, 간선과 같은 그래프 자료구조에 대한 내용은 이곳을 참고해 주세요!
특징
- 음의 간선(0보다 작은 간선)이 없을 때만 동작합니다.
- 최단 경로를 계산할 때 현재 노드에서부터 다른 노드 각각에 대한 최단 거리를 1차원 리스트('최단 거리 테이블'이라 부름)에 저장하며 리스트를 갱신합니다.
- 노드와 간선의 개수가 모두 많을 때 다익스트라 최단 경로 알고리즘을 활용하는 것이 효과적입니다.
- 노드의 개수가 적을 때는 플로이드 워셜 알고리즘을 활용하여 문제를 해결하는 것이 효과적입니다.
- 최단 경로를 선택해 문제를 풀어간다는 점에서 그리디(Greedy) 알고리즘 문제 유형에 속하기도 합니다.
참고: 다익스트라 vs 데이크스트라
다익스트라(Dijkstra) 알고리즘을 개발한 에츠허르 비버 다익스트라(Edsger Wybe Dijkstra)는 네덜란드 컴퓨터 과학자로서 'Dijkstr'의 정확한 외래어 표기법은 '데이크스트라'입니다. 하지만, 국내에서는 주로 '다익스트라'로 불리고 알려져 있다는 점에서 앞으로 '다익스트라'로 표기하겠습니다.
3. 다익스트라 최단경로 알고리즘의 동작 과정
이제 다익스트라 최단 경로 알고리즘의 구체적인 동작 과정을 살펴보겠습니다. 동작 순서는 아래와 같습니다.
1️⃣ 출발 노드를 선택합니다.
2️⃣ 최단 거리 테이블 내 모든 값을 '무한'으로 초기화합니다.
3️⃣ 방문하지 않은 노드 중에서 최단 거리 테이블 내 최단 거리에 있는 노드를 선택합니다.
4️⃣ 선택한 노드를 거쳐 다른 노드로 가는 거리를 각각 계산합니다.
5️⃣ 최단 거리 테이블 내 노드별 거리가 계산한 값보다 클 경우 계산한 값으로 해당 노드의 거리를 갱신합니다.
6️⃣ 위 과정 중 3️⃣~5️⃣ 과정을 반복합니다.
위의 동작 과정 중 "방문하지 않은 노드 중에서 현재 선택된 노드에서 최단거리가 가장 짧은 노드를 탐색한다"라는 점에서, 다익스트라 최단 경로 알고리즘이 그리디 알고리즘 문제 유형에 속한다고 말합니다.
이제 본격적으로 아래 그림 1과 같이 예시 그래프를 통해 다익스트라 최단 경로 알고리즘의 동작 과정을 알아보겠습니다. 그림 1의 그래프에서 노드 1에서 다른 모든 노드로 가는 최단 경로를 구해 보겠습니다.
(1) 먼저, 노드 1을 출발 노드로 설정하겠습니다(과정 1️⃣). (2) 출발 노드에서 다른 모든 노드로 가는 최단 거리를 '무한'으로 초기화합니다. 출발 노드는 노드 1이고, 노드 자기 자신 간의 거리는 0으로 표기합니다(과정 2️⃣).
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 최단 거리 | 0 | 무한 | 무한 | 무한 | 무한 | 무한 |
최단 거리 테이블
(2) 방문하지 않은 노드들 중에서 최단 거리 테이블에서 최단 거리가 가장 짧은 노드인 노드 1을 선택합니다(과정 3️⃣). 이제 노드 1을 거쳐 다른 모든 노드로 가는 거리를 계산합니다(과정 4️⃣). 노드 1을 거치면 노드 2, 4, 5로 갈 수 있습니다. 아래 그림 2에서 현재 처리 중인 노드와 간선은 파란색으로 표현하였습니다. 노드 1까지의 거리는 0이므로 노드 1을 거쳐 노드 2, 4, 5로 가는 거리는 각각 2(0+2), 1(0+1), 3(0+3)입니다. 최단 거리 테이블 내에 노드 2, 4, 5의 최단 거리 값('무한')이 현재 계산한 최단 거리 값보다 크기 때문에, 노드별로 최단 거리를 계산한 값으로 최단 거리 테이블을 갱신합니다(과정 5️⃣).
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 최단 거리 | 0 | 2 | 무한 | 1 | 3 | 무한 |
최단 거리 테이블
(3) 이제 아래 그림 3과 같이 처리가 완료된 노드는 회색으로, 간선은 점선으로 표현하겠습니다. 방문하지 않은 노드들 중에서 최단 거리 테이블 내 최단 거리가 가장 짧은 노드를 선택합니다(과정 3️⃣). 노드 4가 최단거리가 1로 가장 짧기 때문에 노드 4를 선택합니다. 노드 4에서는 노드 3과 5로 갈 수 있습니다. 노드 4까지의 거리가 1이므로 노드 4를 거쳐 노드 3으로 가는 최단 거리는 2(1+1)입니다. 최단 거리 테이블 내 3번 노드의 값이 현재 '무한'이므로 더 짧은 거리 2로 갱신합니다. 노드 4를 거쳐 노드 5로 가는 최단 거리는 4(1+3)이며, 이는 최단 거리 테이블 내 값보다 크기 때문에 노드 5는 더 짧은 거리로 갱신할 수 없습니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 최단 거리 | 0 | 2 | 2 | 1 | 3 | 무한 |
(4) 최단 거리 테이블에서 가장 거리가 짧은 노드 2가 선택됩니다(그림 4 참고). 노드 2를 거쳐 노드 3과 6을 갈 수 있습니다. 각각 최단 거리를 계산하면 5(2+3), 4(2+2)입니다. 현재 최단 거리 테이블 내 노드 3의 최단 거리가 2이므로 더 짧은 거리로서 최단 거리 테이블을 갱신할 수 없습니다. 반면, 노드 6의 최단 거리는 현재 '무한'이므로 더 짧은 거리인 4로 테이블을 갱신할 수 있습니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 최단 거리 | 0 | 2 | 2 | 1 | 4 | 4 |
(5) 최단 거리 테이블에서 가장 거리가 짧은 노드 3이 선택됩니다(그림 5 참고). 노드 3을 거쳐서 방문할 수 있는 2번 노드까지의 최단 거리는 5(2+3)입니다. 하지만, 2번 노드의 현재 최단 거리 테이블 내 최단 거리가 2이므로 더 짧은 거리로 갱신할 수 없습니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 최단 거리 | 0 | 2 | 2 | 1 | 4 | 4 |
(6) 최단 거리 테이블에서 노드를 선택할 때 노드 간의 최단 거리가 같다면 일반적으로 노드 번호가 낮은 노드를 선택합니다 따라서 그림 6와 같이 노드 5를 선택합니다. 위와 같은 방식으로 노드 5를 거쳐 노드 2, 3으로 가는 최단 거리는 각각 9(4+5), 6(4+2)입니다. 따라서 두 노드 모두 최단 거리 테이블을 더 짧은 거리로 갱신할 수 없습니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 최단 거리 | 0 | 2 | 2 | 1 | 4 | 4 |
(7) 이제 그림 7과 같이 노드 6이 선택됩니다. 위와 같은 방식으로 노드 6을 거쳐 노드 3, 4, 5로 가는 최단 거리는 각 9(4+5), 6(4+4), 5(4+1)입니다. 따라서 모든 노드의 최단 거리 테이블을 갱신할 수 없습니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 최단 거리 | 0 | 2 | 2 | 1 | 4 | 4 |
최종 최단 거리 테이블은 아래와 같습니다. 이를 통해 노드 1을 시작해서 노드 2, 3, 4, 5, 6까지 가기 위한 최단 거리는 2, 2, 3, 4, 4라는 것을 알 수 있습니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 최단 거리 | 0 | 2 | 2 | 1 | 4 | 4 |
4. 구현 방법1: 일반적인 방법
다익스트라 알고리즘 구현 방법은 크게 2가지로 나눌 수 있습니다. 2가지 경우를 나누어 구현하는 방법을 각각 알아봅니다. 이번 섹션에서는 단순히 알고리즘 원리를 고려하여 그대로 구현해 봅니다.
(1) 일반적인 구현 방법: 알고리즘 원리를 고려하여 그대로 구현
(2) 시간 복잡도를 고려한 구현 방법
4.1. 코드 해설
초기 셋업
전체 코드를 찾는 분들은 아래에 '4.2. 전체 코드'를 참고하세요 :)
# '무한'을 의미하는 값으로 10억을 활용
INF = int(1e9)
# 노드와 간선의 개수를 각각 입력받기
n, e = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 노드별로 연결된 노드 정보를 저장할 리스트 선언
graph = [[] for i in range(n+1)]
# 방문 이력을 저장할 리스트
visited = [False] * (n+1)
# 최단 거리 테이블: 초기에는 모든 값을 무한으로 초기화
distance = [INF] * (n+1)2줄
파이썬에서 지수 표현식을 그대로 사용하면 실수형으로 반환하기 때문에 정수형 표현을 위해 int를 사용하였습니다.
11줄-15줄
노드 번호 등과 관련된 정보를 저장할 리스트를 활용할 때, 노드 번호와 같은 값의 인덱스를 사용하기 위해 노드 개수보다 1개 더 많게 리스트 원소를 할당하였습니다. 이는 파이썬에서 리스트 내 맨 첫 번째 원소의 인덱스가 0이기 때문이죠.
그래프 내 간선 정보 입력받기
# 간선 정보 입력받기
for _ in range(e):
# 노드 A에서 노드 B로 가는 비용이 cost
n_a, n_b, cost = map(int, input().split())
graph[n_a].append((n_b, cost))노드 A를 거쳐 노드 B로 갈 때의 거리(비용, cost)를 입력하는 코드입니다.
처리할 노드 선택하기
# 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드 번호 반환
def node_choice():
min_v = INF
# 최단 거리가 가장 짧은 노드 번호(=인덱스)
idx = 0
for i in range (1, n+1):
if distance[i] < min_v and not visited[i]:
min_v = distance[i]
idx = i
return idx방문하지 않은 노드 중에서 최단 거리 테이블 내 최단 거리가 가장 짧은 노드를 찾아 노드 번호를 반환하는 함수입니다.
다익스트라 알고리즘 구현
def dijkstra(start):
# 시작 노드의 최단 거리 및 방문이력 초기화
distance[start] = 0
visited[start] = True
# 시작 노드와 연결된 각각의 노드 간의 거리
for i in graph[start]:
distance[i[0]] = i[1]
for i in range(n-1):
# 최단 거리가 가장 짧은 노드를 선택하고 방문처리
n_now = node_choice()
visited[n_now] = True
# 현재 노드를 거쳐 다른 노드까지의 거리 계산
for j in graph[n_now]:
c = distance[n_now] + j[1]
# 최단 거리 테이블 갱신 가능여부 체크
if c < distance[j[0]]:
distance[j[0]] = c3줄-7줄
가장 먼저, 시작 노드와 관련한 정보에 대해 초기화를 실시합니다. 시작 노드의 최단 거리는 0으로 초기화하고 방문 처리합니다. 반복문을 이용해 시작 노드와 연결된 모든 다른 노드들 간의 거리를 각각 계산합니다.
9줄-19줄
현재 방문하지 않은 노드들 중에 최단 거리 테이블 내 최단 거리가 가장 짧은 노드를 찾아서 방문 처리합니다. 해당 노드를 거쳐 다른 노드로 갈 수 있는 경로를 각각 계산합니다.
다익스트라 알고리즘 구동
# 다익스트라 알고리즘 구동
dijkstra(start)
for i in range(1, n+1):
# 노드를 방문할 수 없는 경우, '무한' 값 출력
if distance[i] == INF:
print("INF")
# 노드를 방문할 수 있을 경우, 최단 거리 출력
else:
print("{}번 노드까지 최단 거리: {}".format(i, distance[i]))이제 시작 노드의 번호를 전달 인자로서 구현해 놓은 다익스트라 알고리즘을 동작시킵니다. 반복문을 활용해 시작 노드에서 다른 모든 노드로 가는 최단 거리를 각각 출력합니다. 입력 예시와 출력 결과는 이어지는 섹션인 '4.2. 전체 코드' 내 하단을 참고해 주세요.
4.2. 전체 코드
# '무한'을 의미하는 값으로 10억을 활용
INF = int(1e9)
# 노드와 간선의 개수를 각각 입력받기
n, e = map(int, input().split())
# 시작 노드 번호를 입력받기
start = int(input())
# 노드별로 연결된 노드 정보를 저장할 리스트 선언
graph = [[] for i in range(n+1)]
# 방문 이력을 저장할 리스트
visited = [False] * (n+1)
# 최단 거리 테이블: 초기에는 모든 값을 무한으로 초기화
distance = [INF] * (n+1)
# 간선 정보 입력받기
for _ in range(e):
# 노드 A에서 노드 B로 가는 비용이 cost
n_a, n_b, cost = map(int, input().split())
graph[n_a].append((n_b, cost))
# 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드 번호 반환
def node_choice():
min_v = INF
# 최단 거리가 가장 짧은 노드 번호(=인덱스)
idx = 0
for i in range (1, n+1):
if distance[i] < min_v and not visited[i]:
min_v = distance[i]
idx = i
return idx
def dijkstra(start):
# 시작 노드의 최단 거리 및 방문이력 초기화
distance[start] = 0
visited[start] = True
# 시작 노드와 연결된 각각의 노드 간의 거리
for i in graph[start]:
distance[i[0]] = i[1]
for i in range(n-1):
# 최단 거리가 가장 짧은 노드를 선택하고 방문처리
n_now = node_choice()
visited[n_now] = True
# 현재 노드를 거쳐 다른 노드까지의 거리 계산
for j in graph[n_now]:
c = distance[n_now] + j[1]
# 최단 거리 테이블 갱신 가능여부 체크
if c < distance[j[0]]:
distance[j[0]] = c
# 다익스트라 알고리즘 구동
dijkstra(start)
for i in range(1, n+1):
# 노드를 방문할 수 없는 경우, '무한' 값 출력
if distance[i] == INF:
print("INF")
# 노드를 방문할 수 있을 경우, 최단 거리 출력
else:
print("{}번 노드까지 최단 거리: {}".format(i, distance[i]))입력 예시
노드와 간선의 개수를 각각 입력하세요: 6 13
시작 노드를 설정하세요: 1
1 2 2
1 4 1
1 5 3
2 3 3
2 6 2
3 2 3
4 3 1
4 5 3
5 2 5
5 3 2
6 3 5
6 4 4
6 5 1실행 결과
1번 노드까지 최단 거리: 0
2번 노드까지 최단 거리: 2
3번 노드까지 최단 거리: 2
4번 노드까지 최단 거리: 1
5번 노드까지 최단 거리: 3
6번 노드까지 최단 거리: 44.3. 시간 복잡도
시간 복잡도: 노드 개수의 제곱에 비례
위의 코드로 구현한 알고리즘의 시간 복잡도는 O(V^2) 입니다. 여기서 V(Vertex)는 노드의 개수입니다. 제곱으로 표현되는 이유는 다음과 같습니다. 총 O(V) 번 만큼 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 하며, 현재 노드와 연결된 노드와의 거리를 일일이 체크해야 하기 때문입니다.
시간 복잡도 측면의 한계
시간 복잡도가 O(V^2) 인 만큼 알고리즘 테스트(대회)에서 만일 노드 개수가 10,000개가 넘는 그래프가 주어진다면 위의 코드로 문제를 효율적으로 풀어낼 수 없습니다. 따라서 시간 복잡도를 개선한 구현 방법이 필요합니다. 이어지는 섹션에서 시간 복잡도까지 고려한 구현 방법에 대해 소개해 드립니다.
5. 구현 방법2: 시간 복잡도 개선
우선순위 큐 자료구조를 사용하면 최악의 경우에도 시간 복잡도를 O(ElogV) 로 개선된 알고리즘을 구현할 수 있습니다. 여기서 E는 간선(edge)의 수이며 V는 노드(vertex)의 개수입니다.
5.1. 우선순위 큐(Priority Queue) 자료구조
우선순위 큐(Priority Queue) 자료구조는 말 그대로 우선순위가 가장 높은 데이터를 가장 먼저 추출하는 자료구조입니다. 예를 들어, 우선순위의 기준을 특정 값의 크기로 정하면 최댓값이나 최솟값을 찾아야 하는 경우에 모든 데이터를 일일이 확인하지 않고도 우선순위에 따라 데이터를 추출하면 되기 때문에 훨씬 효율적으로 데이터를 탐색할 수 있습니다. 이번 포스팅에서는 이렇게 간단하게 설명을 드립니다. 우선순위 큐 자료구조에 대한 더욱 자세한 내용은 아래 링크를 참고해 주세요!
[자료구조] 우선순위 큐(Priority Queue)에 대해 알아보자!(+Python 구현)
이번 포스팅에서는 우선순위 큐(Priority Queue)에 대해 알아봅니다. 바로 시작하죠! 목차 1. 우선순위 큐(Priority Queue)란? 2. 힙(Heap) 자료구조 2.1. 힙 자료구조란? 2.2. 우선순위 큐 구현 방식: 리스트 vs.
heytech.tistory.com
5.2. 힙(Heap) 자료구조
우선순위 큐 자료구조를 구현하기 위해서는 힙(Heap) 자료구조에 대해 알아야 합니다. 힙 자료구조는 가장 높은(혹은 가장 낮은) 우선순위(e.g., 최댓값, 최솟값)를 가지는 노드를 빠르게 찾아내기 위해 고안된 완전 이진트리(Complete Binary Tree) 기반의 자료구조입니다. 마찬가지로 자세한 내용은 아래 링크를 참고해 주시고, 지금 당장은 최소 힙 자료구조에 대해서만 이해하고 넘어가시길 바랍니다.
[자료구조] 힙(Heap) 자료구조에 대해 알아보자!(+Python 구현)
오늘은 힙 자료구조에 대해 알아보겠습니다. 바로 시작하죠! 목차 1. 힙 자료구조란? 2. 힙 자료구조는 언제 사용할까? 3. 힙 자료구조의 종류 4. 힙 자료구조의 동작 과정(최소 힙) 4.1. 데이터 삽입
heytech.tistory.com
최소 힙(Min Heap)은 '가장 작은 값이 가장 먼저 추출'된다는 특징을 갖고 있습니다. 즉, 다익스트라 최단 경로 알고리즘은 최대한 비용이 적은 노드를 우선으로 방문한다는 점에서, 최소 힙 구조를 바탕으로 우선순위 큐 자료구조를 구현하면 알고리즘의 시간 복잡도를 개선할 수 있습니다.
5.3. 우선순위 큐 자료구조 기반의 알고리즘 동작 과정
이제 우선순위 큐 자료구조를 적용하여 다익스트라 알고리즘이 동작하는 과정을 살펴보겠습니다. 사실 우선순위 큐 자료구조를 적용해도 다익스트라 최단경로 알고리즘 동작의 기본적인 원리는 변하지 않습니다. 앞서 "3. 다익스트라 최단경로 알고리즘의 동작 과정" 섹션에서 활용했던 최단 거리 테이블은 그대로 사용할 예정이며, 현재 처리 중인 노드로부터 가장 가까운 노드를 저장하기 위한 우선순위 큐 자료구조를 추가로 활용해 보겠습니다.
(1) 그림 8에서 1번 노드를 출발 노드로 설정하겠습니다.최단 거리 테이블 내 출발 노드에서 다른 모든 노드로 가는 최단 거리를 '무한'으로 초기화합니다. 출발 노드에서 자기 자신 간의 거리는 0입니다. 이제 노드 번호와 노드 간의 거리를 하나의 객체로서 (거리: 0, 노드 번호: 1)을 우선순위 큐 자료구조에 삽입합니다.
파이썬에서는 해당 객체를 (0, 1)와 같이 튜플의 형태로 삽입해 주면 됩니다. 특히 파이썬 heapq 라이브러리에서 우선순위 큐 자료구조에 튜플을 입력하면 튜플의 첫 번째 원소가 우선순위를 결정짓는 기준이 됩니다. 따라서 (거리, 노드 번호) 객체를 우선순위 큐 자료구조에 삽입하면 거리순으로 정렬됩니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 최단 거리 | 0 | 무한 | 무한 | 무한 | 무한 | 무한 |
최단 거리 테이블
| 우선순위 큐 | (거리: 0, 노드: 1) |
우선순위 큐 자료구조
(2) 이제 거리가 가장 짧은 노드를 선택해야 합니다. 우선순위 큐 자료구조에 이미 거리가 짧은 순서대로 정렬이 되어 있기 때문에 우선순위 큐에서 최상위 원소를 추출하면 됩니다. 즉, 우선순위 큐에서 추출한 노드 중에서 방문하지 않은 노드만 처리하면 됩니다. 따라서 우선순위 큐에서 최상위 원소를 꺼내면 (0, 1)이 추출됩니다. 이는 1번 노드까지의 거리가 0이라는 의미입니다. 편의상 그림 9와 같이 현재 처리 중인 노드와 간선을 파란색으로 표현하겠습니다. 또한, 방문 이력이 있는 노드와 간선은 회색으로 표현하겠습니다.
이제 1번 노드를 거쳐서 방문할 수 있는 2, 4, 5번 노드로 가는 최단 거리를 각각 계산합니다(그림 9 참고). 2, 4, 5번까지의 최단거리는 각각 2(0+2), 1(0+1), 3(0+3)입니다. 현재 최단 거리 테이블 내 2, 4, 5번 노드까지의 거리가 '무한'이므로 앞서 구한 최단거리 값으로 모든 노드 정보가 갱신됩니다. 이제 이렇게 더 짧은 경로를 찾은 노드 정보와 거리를 우선순위 큐 자료구조에 삽입합니다. 이때 우선순위 큐 내 원소들은 거리가 짧은 순서대로 최상단에 위치하게 됩니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 최단 거리 | 0 | 2 | 무한 | 1 | 3 | 무한 |
최단 거리 테이블
| 우선순위 큐 | (거리: 1, 노드 정보: 4) (거리: 2, 노드 정보: 2) (거리: 3, 노드 정보: 5) |
우선순위 큐 자료구조
(3) 다시 우선순위 큐에서 원소 하나를 추출합니다. (1, 4) 객체가 추출되며 4번 노드는 아직 방문한 이력이 없습니다. 따라서 4번 노드를 거쳐서 방문할 수 있는 노드인 3번과 5번 노드까지의 비용을 계산합니다(그림 10 참고). 4번 노드까지의 최단 거리가 1이므로 3번과 5번 노드까지의 최단 거리는 각각 2(1+1), 4(1+3)입니다. 최단 거리 테이블 내 3번 노드의 값은 '무한'이므로 3번 노드는 더 짧은 거리 정보로 갱신됩니다. 반면, 5번 노드는 4번 노드를 거쳐서 가는 거리가 4로 최단 거리 테이블 내 값보다 크므로 더 짧은 최단 거리를 갱신할 수 없습니다. 따라서 (2, 3) 객체만 우선순위 큐에 삽입합니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 최단 거리 | 0 | 2 | 2 | 1 | 3 | 무한 |
최단 거리 테이블
| 우선순위 큐 | (거리: 2, 노드 정보: 2) (거리: 2, 노드 정보: 3) (거리: 3, 노드 정보: 5) |
우선순위 큐 자료구조
(4) 우선순위 큐에서 원소 하나를 추출합니다. (2, 2) 객체가 추출되며 2번 노드는 방문 이력이 없습니다. 따라서 2번 노드를 거쳐서 방문할 수 있는 노드인 3번과 6번 노드까지의 비용을 계산합니다(그림 11 참고). 2번 노드까지의 최단 거리가 2이므로 3번과 6번 노드까지의 최단 거리는 각각 5(2+3), 4(2+2)입니다. 3번 노드는 2번 노드를 거쳐서 가는 거리가 4로 최단 거리 테이블 내 값보다 크므로 더 짧은 최단 거리를 갱신할 수 없습니다. 반면, 최단 거리 테이블 내 6번 노드의 값은 '무한'이므로 6번 노드는 더 짧은 거리 정보로 갱신됩니다. 따라서 (4, 6) 객체만 우선순위 큐에 삽입합니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 최단 거리 | 0 | 2 | 2 | 1 | 3 | 무한 |
최단 거리 테이블
| 우선순위 큐 | (거리: 2, 노드 정보: 3) (거리: 3, 노드 정보: 5) (거리: 4, 노드 정보: 6) |
우선순위 큐 자료구조
(5) 마찬가지 방식으로 우선순위 큐에서 (2, 3)을 꺼냅니다. 3번 노드는 방문한 이력이 없으므로 3번 노드를 거쳐서 방문할 수 있는 노드인 2번 노드까지의 최단 거리는 5(2+3)입니다 (그림 12 참고). 따라서 최단 거리 테이블을 갱신할 수 없으며 우선순위 큐에도 객체를 삽입할 수 없습니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 최단 거리 | 0 | 2 | 2 | 1 | 3 | 4 |
최단 거리 테이블
| 우선순위 큐 | (거리: 3, 노드 정보: 5) (거리: 4, 노드 정보: 6) |
우선순위 큐 자료구조
(6) 우선순위 큐에서 (3, 5)를 꺼냅니다. 5번 노드는 방문한 이력이 없기 때문에 처리해 줍니다. 5번 노드를 거쳐서 방문할 수 있는 2번, 3번 노드까지의 최단 거리는 각각 8(3+5), 5(3+2)입니다(그림 13 참고). 따라서 최단 거리 테이블을 갱신할 수 없고 우선순위 큐에 어떤 객체도 삽입할 수 없습니다.
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 최단 거리 | 0 | 2 | 2 | 1 | 3 | 4 |
최단 거리 테이블
| 우선순위 큐 | (거리: 4, 노드 정보: 6) |
우선순위 큐 자료구조
(7) 우선순위 큐에서 (4, 6)을 꺼냅니다. 6번 노드는 방문한 이력이 없으므로 처리해 줍니다. 6번 노드를 거쳐서 방문할 수 있는 3, 4, 5번 노드까지의 최단 거리는 각각 9(4+5), 8(4+4), 5(4+1)이기 때문에 최단 거리 테이블을 갱신할 수 없으며 우선순위 큐에 어떤 객체도 삽입하지 못 합니다(그림 14 참고).
| 노드 번호 | 1 | 2 | 3 | 4 | 5 | 6 |
| 최단 거리 | 0 | 2 | 2 | 1 | 3 | 4 |
최단 거리 테이블
| 우선순위 큐 |
우선순위 큐 자료구조
이처럼 최단 거리 테이블에 남아 있는 0, 2, 2, 1, 3, 4가 노드 1을 거쳐 각 노드까지의 최단 거리입니다.
5.4. 우선순위 큐 자료구조 기반의 구현(Python)
import heapq
import sys
input = sys.stdin.readline
# '무한'을 의미하는 값으로 10억을 활용
INF = int(1e9)
# 노드와 간선의 개수를 각각 입력받기
n, e = map(int, input().split() )
# 시작 노드 번호를 입력받기
start = int(input())
# 노드별로 연결된 노드 정보를 저장할 리스트 선언
graph = [[] for i in range(n+1)]
# 최단 거리 테이블: 초기에는 모든 값을 무한으로 초기화
distance = [INF] * (n+1)
# 간선 정보 입력받기
for _ in range(e):
# 노드 A에서 노드 B로 가는 비용이 cost
n_a, n_b, cost = map(int, input().split())
graph[n_a].append((n_b, cost))
def dijkstra(start):
# 우선순위 큐 자료구조 생성
pq = []
# 시작 노드의 자기 자신까지의 거리는 0으로 설정, 우선순위 큐에 삽입
heapq.heappush(pq, (0, start))
distance[start] = 0
# 우선순위 큐가 비어있을 때까지 무한 반복
while pq:
# 최단 거리가 가장 짧은 노드 추출(거리, 노드 정보 순)
dist, n_now = heapq.heappop(pq)
# 이미 처리된 노드는 무시
if distance[n_now] < dist:
continue
# 현재 처리 중인 노드와 인접한 노드 확인
for i in graph[n_now]:
c = dist + i[1]
# 현재 노드를 거쳐 다른 노드로 가는 거리가 더 짧은 경우
if c < distance[i[0]]:
# 최단 거리 테이블 갱신
distance[i[0]] = c
# 우선순위 큐에 (거리, 노드 정보) 삽입
heapq.heappush(pq, (c, i[0]))
# 다익스트라 알고리즘 구동
dijkstra(start)
for i in range(1, n+1):
# 노드를 방문할 수 없는 경우, '무한' 값 출력
if distance[i] == INF:
print("INF")
# 노드를 방문할 수 있을 경우, 최단 거리 출력
else:
print("{}번 노드까지 최단 거리: {}".format(i, distance[i]))구현에 있어서 앞서 살펴본 코드("4.2. 전체 코드" 섹션)와 비교했을 때, node_choice() 함수를 작성할 필요가 없다는 것이 특징입니다. 이는 최단 거리가 가장 짧은 노드를 노드를 선택하는 과정을 다익스트라 최단 경로 알고리즘 함수에서 우선순위 큐를 활용하여 대체하였습니다.
입력 예시
노드와 간선의 개수를 각각 입력하세요: 6 13
시작 노드를 설정하세요: 1
1 2 2
1 4 1
1 5 3
2 3 3
2 6 2
3 2 3
4 3 1
4 5 3
5 2 5
5 3 2
6 3 5
6 4 4
6 5 1실행결과
1번 노드까지 최단 거리: 0
2번 노드까지 최단 거리: 2
3번 노드까지 최단 거리: 2
4번 노드까지 최단 거리: 1
5번 노드까지 최단 거리: 3
6번 노드까지 최단 거리: 4마치며
오늘은 최단경로 알고리즘 중에서도 다익스트라 최단 경로 알고리즘에 대해 알아보았습니다. 특히, 다익스트라 알고리즘의 동작 과정을 예시와 함께 살펴보고 이를 파이썬에서 구현하는 2가지 방법에 대해 각각 알아보고 비교해 보는 시간을 가졌습니다. 이 2가지 구현 방법 중 먼저 살펴본 방식인 알고리즘의 동작 원리를 그대로 구현하는 방식의 시간 복잡도가 O(V^2) 이었습니다. 반면에, 우선순위 큐 자료구조를 기반으로 알고리즘을 구현하면 시간 복잡도가 O(ElogV) 로 노드의 개수가 많아질 때 상대적으로 연산 속도를 더욱 크게 개선할 수 있습니다. 여기에서 V는 노드(Vertex)의 개수이며 E는 간선의(Edge) 개수입니다. 다음 포스팅에서는 다른 최단 경로 알고리즘인 플로이드 워셜 알고리즘에 대해 알아보도록 하겠습니다.
📚참고할 만한 포스팅
1. [자료구조] 우선순위 큐(Priority Queue)에 대해 알아보자!(+Python 구현)
2. [자료구조] 힙(Heap) 자료구조에 대해 알아보자!(+Python 구현)
3. [자료구조] 그래프 자료구조에 대해 알아보자!(노드, 간선)
4. 최단경로(길찾기) 알고리즘#1: 다익스트라 최단 경로 알고리즘에 대해 알아보자! (+Python 구현)
5. 최단경로(길찾기) 알고리즘#2: 플로이드 워셜(Floyd-Warshall) 알고리즘에 대해 알아보자!(+Python 구현)
포스팅 내용에 오류가 있을 경우 댓글 남겨주시면 감사드리겠습니다.
그럼 오늘도 건강한 하루 보내시길 바랍니다 :)
고맙습니다.
'알고리즘 > 이론' 카테고리의 다른 글
| [자료구조] 그래프 자료구조와 트리 자료구조의 차이에 대해 알아보자! (0) | 2021.04.15 |
|---|---|
| 플로이드 워셜(Floyd-Warshall) 알고리즘 이해(+Python 구현) (0) | 2021.04.14 |
| [자료구조] 힙(Heap) 자료구조에 대해 알아보자!(+Python 구현) (2) | 2021.04.11 |
| [자료구조] 우선순위 큐(Priority Queue)에 대해 알아보자!(+Python 구현) (0) | 2021.04.02 |
| [자료구조] 그래프 자료구조에 대해 알아보자!(노드, 간선, 루트 노드, 깊이, 높이, 차수) (0) | 2021.04.01 |
