다익스트라 알고리즘
: 특정 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다.
- 노드 간 간선이 음의 값을 가지지 않아야 함
- 그리디 알고리즘 : 매 상황에서 가장 비용이 적은 노드를 선택함
- 동작 과정
- 출발 노드 설정
- 최단 거리 테이블 초기화 (Inf)
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
- 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
- 3~4번 반복
- 한번 처리된 노드의 최단 거리는 고정됨. 더 이상 바뀌지 않음.
구현 방법 : 순차탐색
매 단계마다 1차원 테이블의 모든 원소를 확인한다.
import sys
input = sys.stdin.readline
INF = int(le9) #10억
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) :
distance[start] = 0
visited[start] = True
for j in graph[start] :
distance[j[0]] = j[1] # 이 부분 이해가 잘 안감
for i in range(n-1) :
now = get_smallest_node()
visited[now] = True
for j in graph[now]:
cost = distance[now] + j[i]
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]) - 시간 복잡도 :
- 코딩테스트에서 전체 노드 개수가 5000개 이하면 해결 가능 > 10,000개를 넘어가는 문제라면?
개선된 구현 방법 : 우선순위 큐
힙(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(h))
return result
result = heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)실행결과 : [0,1,2,3,4,5,6,7,8,9]heappush, heappop : 오름차순 정렬
# 최대 힙
import heapq
def heapsort(iterable):
h = []
result = []
for value in iterable :
heapq.heappush(h, -value) # [-9, -8, -7, -6, -5, -4, -3, -2, -1, 0]
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)실행결과 : [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]오름차순을 음의 값으로 변경해서 내림차순으로 만들기
😎 다시 다익스트라 알고리즘으로 돌아와서,
Heap 자료구조를 이용해 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택한다.
거리가 가장 짧은 노드를 선택해야 하므로 최소 힙을 사용한다.
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 = []
# 시작노드로 가기 위한 거리를 0으로 설정, 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("INF")
else :
print(distance[i])실행결과 :
4 7 #n,m
1 #start
1 2 2 #graph
1 3 5
1 4 1
2 4 2
2 3 3
3 2 3
4 3 3
0 # distance from start to 1
2 # distance from start to 2
4 # distance from start to 3
1 # distance from start to 4- 힙 자료구조를 이용하면 시간복잡도는 가 된다.
- 반복문은 최대 노드의 개수(V)만큼 처리되며, 현재 노드에서 다른 노드들을 확인하는 총 횟수는 최대 간선의 개수(E)만큼 처리된다.
- 직관적으로 전체 과정은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사합니다. (???)
플로이드 워셜 알고리즘
: 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산
- 다익스트라 알고리즘과 마찬가지로, 거쳐가는 노드를 기준으로 알고리즘 수행
- 2차원 테이블 사용
- 다이나믹 프로그래밍 유형
각 단계마다 특정 노드 k를 거쳐가는 경우를 확인
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):
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
#플로이드워셜 알고리즘 수행
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[b][k])
#출력
for a in range(1, n+1):
for b in range(1, n+1):
if graph[a][b] == INF:
print("INF",end=" ")
else:
print(graph[a][b], end=" ")
print()
특징
- 각 단계마다 의 연산 → 총 시간 복잡도 :
