최단경로 알고리즘 : 가장 짧은 경로를 찾는 알고리즘
👉 다양한 문제 상황
1) 한 지점에서 다른 한 지점까지의 최단 경로
2) 한 지점에서 다른 모든 지점까지의 최단 경로
3) 모든 지점에서 다른 모든 지점까지의 최단 경로
👉 각 지점은 그래프에서 노드로 표현하고, 지점 간 연결된 도로는 그래프에서 간선으로 표현
1. 다익스트라 최단 경로 알고리즘
1) 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로 계산
2) 다익스트라 알고리즘은 음의 간선이 없을 때, 정상적으로 동작.
👉 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않는다.
3) 다익스트라 알고리즘은 그리디 알고리즘으로 분류된다.
👉 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복
4) 알고리즘의 동작 과정
- 출발 노드를 설정한다.
- 최단 거리 테이블을 초기화한다.
👉 모든 노드로 가는 경로의 비용을 무한으로, 자기 자신에 대한 비용은 0으로 설정한다. - 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
👉 가장 짧은 노드를 계속해서 선택하기 때문에, 최단 경로는 확실히 결정되기 때문에 바뀌지 않는다. -> 그리디 알고리즘 - 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.
- 위 과정에서 3번과 4번을 반복한다.
📍 정리
1) 그리디 알고리즘 : 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다.
2) 단계를 거치며 한 번 처리된 노드의 최단 거리를 고정되어 더 이상 바뀌지 않는다.
👉 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있다.
3) 다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단 거리 정보가 저장된다.
👉 완벽한 형태의 최단 경로를 구하려면 소스코드에 추가적인 기능을 넣어야 한다.
2. 우선순위 큐(Priority Queue)
우선순위 큐: 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다.
👉 대부분의 프로그래밍 언어에서 표준 라이브러리 형태로 지원한다.
1) 힙(Heap)
- 우선순위 큐를 구현하기 위해 사용하는 자료구조 중 하나
- 최소 힙(Min Heap)과 최대 힙(Max 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)
📍 힙 사용예제 : 최대 힙
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)📍 우선순위 큐를 이용한 다익스트라 알고리즘 동작 과정
👉 튜플의 첫번째 원소를 '거리'로 설정하게 되면, 거리를 기준으로 해서 거리가 작은 원소가 먼저 나올 수 있도록 큐가 구성된다. (최소 힙)
👉 매 단계마다, 우선순위 큐에서 원소를 꺼내서, 해당 노드까지의 거리를 확인한 뒤에 그 노드를 거쳐가는 각각의 경우까지 모두 고려하면 된다.
👉 노드 1을 아직 방문처리 하지 않았기 때문에, 큐에서 꺼낸 원소를 확인해서 노드 1에 대해 방문처리를 할 수 있다.
👉 그 후, 노드 1을 거쳐가는 인접 노드에 대한 최단 거리값을 갱신할 수 있다.
👉 갱신이 될때만, 큐에 해당 갱신된 노드에 대한 정보를 담아주어야 한다.
👉 갱신된 정보에 따라서, 실제 테이블 값을 갱신해주고, 이어서 우선순위 큐까지 데이터를 넣는다.
👉 큐에 넣어줄 때는 갱신된 거리 값으로 넣어준다.
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 노드의 개수, 간선의 개수를 입력받기
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으로 설정하여, 큐에 삽입
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])
2. 플로이드 워셜 알고리즘
플로이드 워셜 알고리즘 : 모든 노드에서 다른 모드 노드까지의 최단 경로를 모두 계산
1) 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. (다만, 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다.)
2) 2차원 테이블에 최단 거리 정보를 저장한다.
3) 다이나믹 프로그래밍 유형에 속한다.
4) 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다.
- a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사한다.
5) 점화식
6) 동작 과정
👉파란색으로 칠한 부분이 갱신된 부분인데, 1번 노드를 거쳐가는 경우를 확인하고 있기 때문에 1번 행과 열에 대해서는 갱신이 되지 않는다. 또한, 자기 자신에서 자기 자신으로 가는 경우도 갱신되지 않는다.
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정
# 노드의 개수 및 간선의 개수를 입력받기
n = int(input())
m = int(input())
# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]
# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
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라고 설정
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[k][b])
# 수행된 결과를 출력
for a in range(1, n + 1):
for b in range(1, n + 1):
# 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
if graph[a][b] == 1e9:
print("INFINITY", end=" ")
# 도달할 수 있는 경우 거리를 출력
else:
print(graph[a][b], end=" ")
print()✅ 시간 복잡도
- 노드의 개수가 N개일때, 알고리즘상으로 N번의 단계를 수행한다.
👉 각 단계마다 O(N^2)의 연산을 통해 현재 노드를 거쳐 가는 모든 경로를 고려한다. - 따라서 플로이드 워셜 알고리즘의 총 시간 복잡도는 O(N^3)이다.
