: 말 그대로 가장 짧은 경로를 찾는 알고리즘
길 찾기 문제라고도 불림
최단 경로의 여러 경우
: 다익스트라 알고리즘
알고리즘 동작 과정
다익스트라 알고리즘 성능
전체 시간 복잡도 : O(V^2)
일반적으로 코딩테스트 문제에서 최단경로 문제 출제시 1초라고 가정하면 노드 개수가 5,000개 이하라면 이 코드로 해결 가능
다만 노드의 개수가 10,000개를 넘어가는 경우 다른 알고리즘 설계 필요
Heap : 우선순위 큐를 구현하기 위해 사용하는 자료구조
최소 힙, 최대 힙
다익스트라 최단경로 알고리즘을 포함해 다양한 알고리즘에서 사용됨
우선선위 큐 구현 방식 | 삽입 시간 | 삭제 시간 |
---|---|---|
리스트 | O(1) | O(N) |
힙 | O(logN) | O(logN) |
Python에서의 구현 방법
heap
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())
return result
result = heapsort([1, 3, 5, 7, 9])
print(result)
💡 Python에서 최대 힙 사용하고 싶다면?
원소 부호를 바꿔서 넣고, 뺄 떄 다시 부호 바꿔주기
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split())
start = int(input())
graph = [[] for i in range(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 = heqpq.heqppop(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 graph:
if distance[i] == INF:
print("INFINITY")
else:
print(distance[i])
개선된 다익스트라 알고리즘 성능(ft. 우선순위 큐)
모든 노드에서 다른 모든 노드까지의 최단 경로
노드의 개수가 적은 경우 유용. 노드/간선이 많은 경우 다익스트라가 나음
O(N^3)
점화식
Python으로 플루이드 워셜 알고리즘 구현
# set infinite number
INF = int(1e9)
# get the number of nodes and edges
n = int(input())
m = int(input())
# create 2 dimensional list, set INF
graph = [[INF] * (n + 1) for _ in range(n + 1)]
# set 0 for the distances from a node to the node itself
for a in range(1, n + 1):
for b in range(1, n + 1):
if a == b:
graph[a][b] = 0
# get the input of edges information
for _ in range(m):
a, b, c = map(int, input().split())
graph[a][b] = c
# floyd-warshall algorithm
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])
# print the result
for a in range(1, n + 1):
for b in range(1, n + 1):
# if not reachable, print infinity
if graph[a][b] == INF:
print("Infinity", end = " ")
# if reachable, print the distance
else:
print(graph[a][b], end = " ")
print()