모눈종이에 사각사각
최단 경로(Shortest Path) 알고리즘 본문
이번 포스팅에서는 최단 경로 알고리즘에 대해 다뤄보고자 한다.
최단경로 알고리즘은 이름에도 나와있듯이 가장 짧은 경로를 찾는 알고리즘이다. '길찾기' 문제라고도 불린다.
최단경로 알고리즘은 대표적으로 세 가지가 있다.(컴공 학부수준)
1. 다익스트라 알고리즘
2. 플로이드 워셜 알고리즘
3. 벨만 포드 알고리즘
1, 2번이 코딩테스트에서 가장 많이 등장하는 유형이라고 한다.
먼저 다익스트라 최단 경로 알고리즘에 대해 알아보고자 한다.
🥝 다익스트라 최단 경로 알고리즘 -> 한 지점에서 다른 모든 지점까지의 최단 경로
- 특정한 노드에서 출발하여 다른 노드로 가는 최단 경로를 구해주는 알고리즘
- 기본적으로 그리디 알고리즘으로 분류 (매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문)
동작 과정
1. 출발노드 설정
2. 최단 거리 테이블 초기화 -> 모두 무한대로 설정
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
5. 3, 4번 반복
- '각 노드에 대한 현재까지의 최단 거리'정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신
- 매번 현재 처리하고 있는 노드를 기준으로 주변 간선 확인
- 한 번 선택된 노드는 최단 거리가 감소하지 않는다. \(\rightarrow\) 마지막 노드에 대해서는 확인할 필요가 없다.
왜 한 번 선택된 노드는 최단 거리가 감소하지 않을까?
현재까지 최단 거리로 도착한 노드에서 뻗어나가는 노드이기 때문이지 않을까?
🥦 방법1. 간단한 다익스트라 알고리즘
# 간단한 다익스트라 알고리즘
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한대 설정
n, m = map(int, input().split()) # n 노드의 개수, m 간선의 개수
start = int(input()) # 시작노드
graph = [[] for _ in range(n+1)] # 각 노드에 연결되어 있는 노드에 대한 정보
visited = [False]*(n+1) # 노드 방문 기록
distance = [INF]*(n+1) # 최단거리 테이블
for _ in range(m):
a, b, c = map(int, input().split())
# a번 노드에서 b번노드로, 비용은 c
graph[a].append((b, c))
def get_smallest_node():
min_value = INF
index = 0
for i in range(1, n+1):
if distance[i] < min_value and not visited[i]:
# 거리가 짧고 아직 방문하지 않았다면
min_value = distance[i]
index = i
return index
def dijkstra(start):
distance[start] = 0 # 시작 노드는 거리 0
visited[start] = True # 시작노드 방문처리
for i in graph[start]:
distance[i[0]] = i[1]
for _ in range(n-1):
now = get_smallest_node() # 가장 거리가 짧은 인덱스
visited[now] = True # 방문처리하고
for j in graph[now]: # 그 노드에서 뻗어나갈 수 있는 부분 탐색
cost = distance[now]+j[1]
distance[j[0]] = min(distance[j[0]], cost) # 원래 거리 vs 갱신된 거리
dijkstra(start)- 시간복잡도 \(O(V^2)\) (* \(V\)는 노드의 개수)
- 총 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형탐색해야함.
따라서 전체 시간 복잡도는 \(O(V^2)\)
=> 노드의 개수가 5,000개 이하라면 괜찮지만, 10,000개를 넘어가는 문제라면 다른 방법을 생각해야함.
🥦 방법2. 개선된 다익스트라 알고리즘
- 최악의 경우에도 \(O(ElogV)\)를 보장 (* \(V\)는 노드의 개수, \(E\)는 간선의 개수)
노드의 개수는 탐색할 수록 줄어들고 \(\rightarrow logV\)
간선의 개수만큼 탐색하기 때문 \(\rightarrow E)
- 최단 거리가 가장 짧은 노드를 찾기 위해(get_smallest_node()) 매번 최단 거리 테이블을을 선형적으로 탐색함.
-> 이 과정에서만 \(O(V)\)의 시간이 걸림 => 이를 줄일 수 있다면!!
- 힙(Heap) 자료구조는 우선 순위 큐를 구현하기 위하여 사용하는 자료구조 중 하나.
- 우선순위 큐 : 우선순위가 가장 높은 데이터를 가장 먼저 삭제
- 파이썬에서는 우선순위 큐가 필요할 때 PriorityQueue 혹은 heapq를 사용, heapq가 더 빠르게 동작하기 때문에 수행 시간이 제한된 상황에서는 heapq 사용 권장
- 파이썬의 우선순위 큐 라이브러리는 최소 힙에 기반
- 힙(Heap) 자료구조 사용 -> 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해
- 다익스트라 알고리즘이 동작하는 기본 원리는 동일하지만, 현재 가장 가까운 노드를 저장해 놓기 위해서 힙 자료를 추가적으로 이용한다는 점이 다름
- 현재 가장 가까운 노드 저장하기 위한 목적으로만 우선 순위 큐를 추가로 이용
# 개선된 다익스트라 알고리즘
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split()) # n 노드의 개수, m 간선의 개수
start = int(input()) # 시작노드
graph = [[] for _ in range(n+1)] # 각 노드에 연결되어 있는 노드에 대한 정보
# visited 리스트 사용하지 않음
distance = [INF]*(n+1) # 최단거리 테이블
for _ in range(m):
a, b, c = map(int, input().split())
# a번 노드에서 b번노드로, 비용은 c
graph[a].append((b, c))
def dijkstra(start):
q = []
# 시작 노드로 가기 위한 최단 경로는 0으로 설정하여 큐에 삽입
heapq.heappush(q, (0, start))
distance[start] = 0
while q: # 큐가 비어있지 않다면
# 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
dist, now = heapq.heappop(q)
# 현재 노드가 이미 처리 된 적이 있는 노드라면 무시
# distance에는 node에 대한 거리 정보가 들어있음.
# 들어 있는 정보가 dist보다 짧다면 이미 방문한 것.
if distance[now] < dist:
continue
for i in graph[now]:
cost = dist + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
dijkstra(start)
🥝 플로이드 워셜 알고리즘 -> 모든 지점에서 다른 모든 지점까지의 최단 경로
- 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산
- 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요 없음
- 각 단계마다 \(O(N^2)\)의 연산을 통해 '현재 노드를 거쳐가는 모든 경로'고려
- 시간복잡도는 \(O(V^3)\)
- 2차원 테이블에 최단 거리 정보를 저장
- 다이나믹 프로그램 유형에 속함
- K번의 단계에 대한 점화식 --> \(D_{ab} = min(D_{ab}, D_{ak}+D_{kb})\)
- A에서 B로 가는 최소 비용과, A에서 K를 거쳐 B로 가는 비용 중 더 작은 값으로 갱신
# 플로이드 워셜 알고리즘
INF = int(1e9)
n,m = map(int,input().split()) # n: 노드의 개수, m: 간선의 개수
graph = [[INF] * (n+1) for _ in range(n+1)] # 2차원 리스트를 만들고, 무한대로 초기화
for i in range(1,n+1):
graph[i][i] = 0 # 자기 자신으로 가는 비용은 0
for _ in range(m):
a,b,c = map(int,input().split())
graph[a][b] = c # 각 간선에 대한 정보를 입력받아 그 값으로 초기화
for k in range(1, n+1):
for a in range(1,n+1):
for b in range(1, n+1):
graph[a][b] = map(graph[a][b], graph[a][k]+graph[k][b])
🥝 벨만 포드 알고리즘 -> 한 지점에서 다른 노드까지의 최단 경로
- 음의 간선이 포함된 상황에서도 구할 수 있다.
- 음수 간선의 순환을 감지할 수 있다.
- 벨만-포드 알고리즘은 매번 모든 간선을 전부 확인한다.
* 음수 간선의 순환
위의 오른쪽 그림을 보면, 1+2+(-4)<0이기 때문에 음수 간선의 순환이 있는 것이다.
- 음수 간선 순환을 확인하는 이유
-> 최단 거리가 음의 무한인 노드가 발생하기 때문
음수 간선에 관하여 최단 경로 문제 분류
1) 모든 간선이 양수인 경우 -> 다익스트라
2) 음수 간선이 있는 경우 -> 벨만-포드
2-1) 음수 간선 순환은 없는 경우
2-2) 음수 간선 순환이 있는 경우
다익스트라 알고리즘 vs 벨만-포드 알고리즘
| 다익스트라 알고리즘 | 벨만-포드 알고리즘 |
| - 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 - 음수의 간선이 없다면 최적의 해를 찾을 수 있음(음수의 간선이 있다면 불가능) 0 속도가 빠름 |
- 매번 모든 간선을 전부 확인 - 다익스트라 알고리즘에서의 최적의 해를 항상 포함 - 음수의 간선이 있어도 최적의 해를 찾을 수 있음 - 음수 간선 순환을 탐지 가능 - 시간 복잡도 느림 \(O(VE)\) |
동작과정
1. 출발 노드 설정
2. 최단 거리 테이블 초기화
3. 다음의 과정을 N-1번 반복
3-1. 모든 간선 E개를 하나씩 확인
3-2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
- 만약 음수 간선 순환이 발생하는 지 체크하고 싶다면 3번의 과정을 한 번 더 수행
->이때 최단 거리 테이블이 갱신된다면 음수 간선이 존재하는 것!
# 벨만 포드 알고리즘
import sys
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split()) # n: 노드의 개수, m: 간선의 개수
edges = [] # 모든 간선에 대한 정보를 담는 리스트
dist = [INF]*(n+1) # 최단 거리 테이블 무한으로 초기화
for _ in range(m):
a, b, c = map(int, input().split())
edges.append((a, b, c)) # a번 노드에서 b번 노드로 가는 비용이 c
def bf(start):
dist[start] = 0 # 시작 노드 초기화
for i in range(n): # n번 라운드 반복
for j in range(m): # 매번 모든 간선 확인
cur = edges[j][0] # 현재 노드
next_node = edges[j][1] # 다음 노드
cost = edges[j][2] # 비용
if dist[cur] != INF and dist[next_node] > dist[cur]+cost:
# 현재의 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧으면
dist[next_node] = dist[cur]+cost
if i == n-1: # n번 째 라운드에서도 값이 갱신된다면 -> 음수 순환 존재
return True
return False
negative_cycle = bf(1) # 시작노드 -> 1번
if negative_cycle:
print("-1")
else:
for i in range(2, n+1): # 1번 노드를 제외한 다른 모든 노드로 가기 위한 최단거리 출력
if dist[i] == INF:
print("-1")
else:
print(dist[i])
📚 참고 : 이것이 취업을 위한 코딩테스트다 with 파이썬
'Algorithm' 카테고리의 다른 글
| 0-1 BFS 알고리즘 (0) | 2022.04.08 |
|---|---|
| 다이나믹 프로그래밍(Dynamic Programming, DP, 동적계획법) (0) | 2022.02.18 |
| 이진 탐색, 이진 탐색 트리 (0) | 2021.09.12 |
| 정렬 (Sorting) (0) | 2021.09.12 |
| DFS/BFS (0) | 2021.09.11 |
