<aside> 🔥 다익스트라 최단 경로 알고리즘?
그래프에서 여러개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단경로를
구해주는 알고리즘으로 GPS소프트웨어의 기본 알고리즘으로 채택되곤 한다.
알고리즘 간단 설명
<aside> 🔥 다익스트라 네이티브 코드
다익스트라 알고리즘 원리
1. 출발지를 s로 정하고, 다음과 같이 표시한다.
(s, t, x, y, z 순)
거리 = [0, inf, inf, inf, inf]
방문 = [True, False, False, False, False]
2. 갈 수 있는 노드들의 최소거리를 측정한다.
s->t: 10
s->y: 5
(s, t, x, y, z 순)
거리 = [0, 10, inf, 5, inf]
방문 = [True, False, False, False, False]
3. 방문 안한 녀석들 중 가장 가까운 녀석인 y를 방문하고, 최소거리를 측정한다.
y->t: 3
y->x: 9
y->z: 2
(s, t, x, y, z 순)
거리 = [0, 8, 14, 5, 7]
방문 = [True, False, False, True, False]
4. 방문 안한 녀석들 중 가장 가까운 녀석인 z를 방문하고, 최소거리를 측정한다.
z->x: 6
(s, t, x, y, z 순)
거리 = [0, 8, 13, 5, 7]
방문 = [True, False, False, True, True]
5. 방문 안한 녀석들 중 가장 가까운 녀석인 t를 방문하고, 최소거리를 측정한다.
t->x: 1
t->y: 2
(s, t, x, y, z 순)
거리 = [0, 8, 9, 5, 7]
방문 = [True, True, False, True, True]
6. 방문 안한 녀석들 중 가장 가까운 녀석인 x를 방문하고, 최소거리를 측정한다.
x->z: 4
(s, t, x, y, z 순)
거리 = [0, 8, 9, 5, 7]
방문 = [True, True, True, True, True]
7. 방문 안한 노드가 없으므로 끝낸다.
(s, t, x, y, z 순)
거리 = [0, 8, 9, 5, 7]
방문 = [True, True, True, True, True]
코드로 구현
입력값은 txt파일로부터 불러오도록 하고 그래프를 생성해준다.
import sys
with open('test_case1.txt') as f:
sys.stdin = f
input = sys.stdin.readline
n, m = map(int, input().split())
start = int(input())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
a, b, c = map(int, input().split())
graph[a].append((b, c))
해당 예시의 그래프는 튜플로 전달되어 (노드번호, 거리)로 저장된다.
// 예시의 그래프
[[], [(2, 2), (3, 5), (4, 1)], [(3, 3), (4, 2)], [(2, 3), (6, 5)], [(3, 3), (5, 1)], [(3, 1), (6, 2)], []]
먼저 최소거리의 노드의 인덱스를 구해주는 함수를 작성한다.
최소값을 우선 무한대로 지정해주고 방문하지 않은 곳 중 가장 짧은 거리의 인덱스를 구해준다.
def get_smallest_node():
min_value = INF # 최소값 무한대로 지정
idx = 0 # 인덱스 초기화
# 전체 그래프 돌면서
for i in range(1, N):
# 노드의 거리가 최소값보다 작고 방문하지 않았다면
if dist[i] < min_value and not visited[i]:
min_value = dist[i] # 최소값을 노드의 거리로 지정
idx = i
return idx
방문 목록과 거리 목록을 리스트의 길이만큼 지정해주고,
첫번째 노드를 방문처리 해준다.
N = len(graph)
# 방문목록, 거리목록 지정
visited = [False] * N
dist = [INF] * N
# 첫번째 노드 방문 처리
visited[start] = True
dist[start] = 0
첫번째 노드의 인접노드의 거리를 확인하여 거리목록에 업데이트 해준다.
for adj, d in graph[start]:
# 거리목록에 인접노드들 거리 지정
dist[adj] = d
첫번째 노드에서 가장 짧은 거리의 노드를 구해서 방문처리를 해주고
거리를 누적으로 업데이트 해준다.
# 첫번쨰 노드 방문했기 때문에 N-1 만큼 반복
for _ in range(N - 1):
# 최소 거리의 노드의 인덱스
cur = get_smallest_node()
# 방문 처리
visited[cur] = True
# 최소 거리의 인접노드와 거리 확인
for adj, d in graph[cur] :
# 누적 거리 계산
cost = dist[cur] + d
# 지정되어있던 거리보다 누적거리가 짧은 경우 거리 바꿈
if cost < dist[adj] :
dist[adj]= cost
return dist
<aside> 🔥 네이티브 코드의 시간 복잡도는 O(V^2)이다.
총 O(V)에 걸쳐서 최단거리가 짧은 노드를 탐색해야하고, 그 노드와 연결된 노드를
매번 확인해줘야하기 때문이다.
따라서 다음 부분에 개선된 다익스트라 알고리즘을 알아보자.
</aside>
</aside>
<aside> 🔥 개선된 다익스트라 알고리즘
개선된 알고리즘은 O(간선의 개수 log (노드의개수))를 보장할 수 있다고 한다.
최단거리를 선형식으로 탐사하는 것이 아닌 최소 힙을 사용해서 더 빠르게 탐색할 수 있다.
<aside> 🔥 힙 자료구조
힙은 우선순위 큐를 구현하기 위하여 사용하는 자료구조 중 하나.
우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징
파이썬에서는 우선순위큐로 PriorityQueue 혹은 heapq 사용 가능하지만,
시간이 제한된 상황에서 heapq를 쓰자.
</aside>
코드로 구현
입력값은 txt파일에 저장해서 받아오도록 하고 이를 토대로 그래프를 생성한다.
import sys
with open('test_case1.txt') as f:
sys.stdin = f
input = sys.stdin.readline
n, m = map(int, input().split())
start = int(input())
graph = [[] for _ in range(n + 1)]
for _ in range(m):
a, b, c = map(int, input().split())
graph[a].append((b, c))
최소 힙으로 우선순위 큐 기능을 구현하고 시작 노드를 방문한다.
여기서 방문처리는 거리 테이블에 값이 저장되면 방문처리된것으로 간주한다.
힙은 튜플형태로 저장될 경우 앞쪽 인덱스를 기준으로 정렬하기 때문에
(거리, 노드)의 튜플 형태로 힙에 저장하도록 한다.
N = len(graph)
dist = [INF] * N # 거리 테이블 지정
# 힙에는 튜플로 저장되며 (거리, 노드)로 저장된다.
q = []
heapq.heappush(q, (0,start))
# 첫 시작점 거리 0
dist[start] = 0
힙에 값이 있는동안 반복하며 힙에서 거리가 가장 짦은 노드를 꺼낸다.
while q :
acc, cur = heapq.heappop(q)
기존에 저장되어있던 거리가 꺼내서 확인한 노드의 거리보다 작으면 확인할 필요가 없으므로
건너뛰도록 한다.
# 해당 노드의 거리가 확인하는 길이보다 짧으면
# 확인할 필요없이 건너뛴다.
if dist[cur] < acc :
continue
인접 노드를 방문하도록 한다.
여기서 거리가 더 짧으면 업데이트하고 큐에 넣어준다.
# 새로 누적된 거리가 더 짧다면
if cost < dist[adj] :
# 업데이트
dist[adj] = cost
# heap에 추가
heapq.heappush(q, (cost, adj))
</aside>