최단 경로 알고리즘
가장 짧은 경로를 찾는 알고리즘
다익스트라 알고리즘
특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산
- 음의 간선이 없을 때 정상 동작
- 그리디 알고리즘으로 분류
동작 과정
- 출발 노드를 설정
- 최단 거리 테이블을 초기화
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신
- 위 과정에서 3번과 4번 반복
예제 코드
INF = 1000000000
n, m = 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(m):
a, b, c = map(int, input().split())
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):
visited[start] = True
distance[start] = 0
for i in graph[start]:
distance[i[0]] = i[1]
for i in range(n-1):
now = get_smallest_node()
visited[now] = True
for j in graph[now]:
if distance[j[0]] > distance[now] + j[1]:
distance[j[0]] = distance[now] + j[1]
dijkstra(start)
for i in range(1, n+1):
if distance[i] == INF:
print(f'{i} = infinity')
else:
print(f'{i} = {distance[i]}')
# 6 11
# 1
# 1 2 2
# 1 3 5
# 1 4 1
# 2 3 3
# 2 4 2
# 3 2 3
# 3 6 5
# 4 3 3
# 4 5 1
# 5 3 1
# 5 6 2성능
전체 시간 복잡도는 O(V^2)이다. 전체 노드의 개수가 5000개 이하면 해결 가능하지만 노드 개수가 10000을 넘어가면 문제 발생
💡 Heap(번외)
우선순위 큐를 구현하기 위해 사용하는 자료구조
- 최소 힙(Min Heap)과 최대 힙(Max Heap)이 있다
- 리스트로 우선순위 큐 구현시 삽입 = O(1), 삭제 = O(N)
힙으로 구현시 삽입 = O(logN), 삭제 = O(logN) - 파이썬의 경우 최소 힙 라이브러리를 지원하고, 최대 힙은 코드를 수정해서 사용한다
최소 힙 예제
import heapq
def heapsort(iterable):
h = []
result = []
for value in iterable:
heapq.heappush(h, value)
for i in range(len(h)):
result.append(heapq.heappop(h))
return result
result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(result)최대 힙 예제
import heapq
def heapsort(iterable):
h = []
result = []
for value in iterable:
heapq.heappush(h, -value)
for i in range(len(h)):
result.append(-heapq.heappop(h))
return result
result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(result)Heap을 이용한 다익스트라
import heapq
INF = 1000000000
n, m = map(int, input().split())
start = int(input())
graph = [[] for i in range(n+1)]
distance = [INF] * (n + 1)
heap = []
for _ in range(m):
a, b, c = map(int, input().split())
graph[a].append((b, c))
def dijkstra(start):
heapq.heappush(heap, [0, start])
distance[start] = 0
while heap:
dist, now = heapq.heappop(heap)
if distance[now] < dist:
# visited를 사용하지 않는 대신 만약 INF가 아니고 dist가 distance[now]보다 크다면,
# 이미 다른 길을 거쳐서 방문했던 적이 있는(더 단거리 경로가 있는) 상황이기 때문에 넘긴다.
continue
for i in graph[now]:
cost = dist + i[0]
if cost < distance[i[1]]:
distance[i[1]] = cost
heapq.heappush(heap, [cost, i[1]])
dijkstra(start)
for i in range(1, n+1):
if distance[i] == INF:
print(f'{i} = infinity')
else:
print(f'{i} = {distance[i]}')
# 6 11
# 1
# 1 2 2
# 1 5 3
# 1 1 4
# 2 3 3
# 2 2 4
# 3 3 2
# 3 5 6
# 4 3 3
# 4 1 5
# 5 1 3
# 5 2 6이와 같이 Heap을 이용해 다익스트라 알고리즘을 구현하면, 최대 간선의 수는 노드의 제곱이기 때문에 O(ElogE) -> O(ElogV^2) -> O(2ElogV) -> O(ElogV)로 표현이 가능합니다.
플로이드-워셜 알고리즘
모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산
- 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘 수행
- 다이나믹 프로그래밍 유형에 속한다
동작 과정
이런 식으로 모든 노드를 거쳐가는 경우의 수 별로 테이블 전체를 업데이트해서 진행한다
예제 코드
INF = int(1e9)
n = int(input())
m = int(input())
graph = [[INF] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, n + 1):
if i == j:
graph[i][j] = 0
for _ in range(m):
a, b, c = map(int, input().split())
graph[a][b] = c
for i in range(1, n + 1):
for j in range(1, n + 1):
for k in range(1, n + 1):
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
for i in range(1, n + 1):
for j in range(1, n + 1):
if graph[i][j] == INF:
print("INFINITY", end=" ")
else:
print(graph[i][j], end=" ")
print()성능
전체 시간 복잡도는 O(N^3)이다. 노드가 500개 이상일 때 500^3이기 때문에 시간이 넉넉하지 않을 수 있다 고로 노드가 500이하 일 때 사용
예제
1.
💡 풀이
import sys
import heapq
INF = int(1e9)
input = sys.stdin.readline
n, m, c = map(int, input().split())
graph = [[] for i in range(n + 1)]
for i in range(m):
x, y, z = map(int, input().split())
graph[x].append([y, z])
def dijkstra(start):
heap = []
distance = [INF] * (n + 1)
heapq.heappush(heap, [0, start])
distance[start] = 0
while heap:
dist, now = heapq.heappop(heap)
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(heap, [cost, i[0]])
return distance
distance = dijkstra(c)
cnt = 0
max_distance = 0
for i in distance:
if i < INF:
cnt += 1
max_distance = max(max_distance, i)
print(cnt - 1, max_distance)먼저 다익스트라를 이용하여 최소 비용 테이블을 만든다. 그리고 distance의 요소 중에 INF보다 작은 것이 도달할 수 있는 도시니까 카운트와 비용의 max값을 비교한다.
2.
💡 다익스트라를 이용
import sys
import heapq
INF = int(1e9)
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [[] for i in range(n + 1)]
for i in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
x, k = map(int, input().split())
def dijkstra(start):
heap = []
distance = [INF] * (n + 1)
heapq.heappush(heap, [0, start])
distance[start] = 0
while heap:
dist, now = heapq.heappop(heap)
if distance[now] < dist:
continue
for i in graph[now]:
cost = dist + 1
if cost < distance[i]:
distance[i] = cost
heapq.heappush(heap, [cost, i])
return distance
cost = dijkstra(1)[k] + dijkstra(k)[x]
if cost >= INF:
print(-1)
else:
print(cost)다익스트라도 마찬가지로 이전 문제와 동일하게 구현한다. 그리고 거쳐가야하기 때문에 1->k와 k->x의 최소비용을 더하여 구할 수 있다.
💡 플로이드-워셜 이용
import sys
import heapq
INF = int(1e9)
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [[INF] * (n + 1) for i in range(n + 1)]
for i in range(m):
a, b = map(int, input().split())
graph[a][b] = 1
graph[b][a] = 1
for i in range(len(graph)):
for j in range(len(graph[i])):
if i == j:
graph[i][j] = 0
x, k = map(int, input().split())
for i in range(1, n + 1):
for j in range(1, n + 1):
for k in range(1, n + 1):
graph[i][k] = min(graph[i][k], graph[i][j] + graph[j][k])
distance = graph[1][k] + graph[k][x]
if distance >= INF:
print(-1)
else:
print(distance)플로이드 워셜로 문제를 풀면 문제 파라미터들을 정의하고 3중 for문으로 거쳐가는 모든 경우의 수를 계산한다.
이게 왜 틀리지... (나의 메모용 블로그)