최단거리 알고리즘
- 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 그대로 적용됨.
- 다이스트라
- 플로이드 워셜
- 벨만 포드
다익스트라 최다 경로 알고리즘
- 음의 간선이 없을 때 정상적으로 작동.
- 매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문에 그리디 알고리즘으로 분류.
- ‘각 노드에 대한 현재까지의 최단 거리 정보’를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신.
- 과정
- 출발 노드 설정
- 최단 거리 테이블 초기화
- ‘방문하지 않은 노드 중’에서 최단 거리가 가장 짧은 노드 선택
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
- 3번과 4번 과정을 반복
간단한 버전
import sys
input = sys.stdin.readline
INF = int(1e9)
n,m = map(int, input().split())
start = int(input())
graph = [[] fo i 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
visited[start] = True
for j in graph[start]: # 시작 노드와 연결된 노드로 가는 cost 갱신
distance[j[0]] = j[1]
for i in range(n-1): # 나머지 노드에 대해서 가장 cost가 작은 노드를 찾고 최단거리 갱신
now = get_smallest_node()
visited[now] = True
for j in graph[now]:
cost = distance[now] + j[1]
if cost < distance[j[0]]
distance[j[0]] = cost
dijkstra(start)
for i in range(1, n+1):
if distance[i] == INF:
print("INFINITY")
else:
print(distance[i])
- 시간 복잡도는 O(V2). 왜냐하면 O(V)에 걸쳐서 최단 거리가 가장 짧은 노드를 선형 탐색해야 하고, 현재 노드와 연결된 노드를 매번 일일이 확인해야하기 때문.
- 전체 노드의 개수가 5000개 이하라면 괜찮지만, 100000개가 넘어가면 사용 불가.
구현은 어렵지만 더 빠른 버전
- 최악의 경우에도 시간 복잡도 O(ElogV) 보장
- 최단 거리가 가장 짧은 노드를 찾기 위해서 O(V)의 시간을 소요했던 것을 개선.
힙 자료구조
- 우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나.
- 우선순위가 가장 높은 데이터를 가장 먼저 삭제. (Queue는 가장 먼저 삽입된 데이터를 먼저 삭제했던 것과 비슷)
- heapq 사용
- 우선순위 값을 표현할 때는 일반적으로 정수형 자료형의 변수가 사용됨.
- 우선순위 큐 라이브러리에 데이터 묶음을 넣으면, 첫 번째 원소를 기준으로 우선순위를 설정.
- 힙 자료구조에서는 N개의 자료를 삽입(삭제)할 때 O(NlogN)의 연산이 필요. 반면 리스트를 사용하면 삽입(삭제)할 때 하나의 원소를 삽입(삭제)할 때 O(N)만큼의 시간이 걸리므로 N개 모두 삽입(삭제)하려면 O(N2) 만큼의 시간이 걸린다.
import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)
n,m = map(int, input().split())
start = int(input())
graph = [[] fo i 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 dijkstra(start):
q = []
heapq.heappush(q, (0,start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
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)
for i in range(1, n+1):
if distance[i] == INF:
print("INFINITY")
else:
print(distance[i])
- E (특정 노드에 연결된 노드의 개수)개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사. 앞에서 말했듯이 힙에 N개의 데이터를 모두 넣고, 이후에 모두 빼는 과정은 O(NlogN)이다. 따라서 간단하게 생각하면 전체 시간 복잡도는 O(ElogE)이다.
- 이때 중복 간선을 포함하지 않는다면, E는 V2보다 항상 작다. 따라서 O(logE) < O(logV)이다.
- 그러므로 시간 복잡도는 O(ElogV)이다.
플로이드 워셜 알고리즘
- 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 쓰이는 알고리즘이다.
- 다익스트라는 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택하고, 해당 노드를 거쳐 가는 경로를 확인하며, 최단 거리 테이블을 갱신.
- 반면, 플로이드 워셜 알고리즘은 ‘거쳐 가는 노드’를 기준으로 알고리즘을 수행. 노드가 N개라면 각각의 노드에서 O(N2)만큼의 연산을 수행해서 ‘현재 노드를 거쳐 가는’ 모든 경로를 고려. 따라서 시간 복잡도는 O(N3).
- 플로이드 워셜 알고리즘에서는 현재 확인하고 있는 노드를 제외하고, N-1개의 노드 중에서 서로 다른 노드 (A,B)쌍을 선택한다. 이후에 A -> 확인하고 있는 노드 -> B로 가는 비용을 계산한 뒤에 최단 거리를 갱신.
- 위 과정을 점화식으로 표현하면 Dab = min(Dab, Dak+Dkb)이다.
- 플로이드 워셜 알고리즘은 2차원 리스트에 ‘최단 거리’ 정보를 저장해야 한다.
- 플로이드 워셜 알고리즘은 다이나믹 프로그래밍이다.
INF = int(1e9)
n = int(input()) # 노드 개수
m = int(input()) # 간선 개수
graph = [[INF] * (n+1) for _ in range(n+1)]
for a in range(1, n+1): # self-connection은 0으로.
for b in range(1, n+1):
if a == b:
graph[a][b] = 0
for _ in range(m):
a,b,c = map(int, input().split())
graph[a][b] = c # 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] = min(graph[a][b], graph[a][k] + graph[k][b])
Comments